home *** CD-ROM | disk | FTP | other *** search
/ Ultra Pack / UltraComputing Partner Applications.iso / SunLabs / tclTK / src / tk4.0 / tkTextBTree.c < prev    next >
C/C++ Source or Header  |  1995-01-03  |  79KB  |  2,790 lines
  1. /* 
  2.  * tkTextBTree.c --
  3.  *
  4.  *    This file contains code that manages the B-tree representation
  5.  *    of text for Tk's text widget and implements character and
  6.  *    toggle segment types.
  7.  *
  8.  * Copyright (c) 1992-1994 The Regents of the University of California.
  9.  * Copyright (c) 1994-1995 Sun Microsystems, Inc.
  10.  *
  11.  * See the file "license.terms" for information on usage and redistribution
  12.  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  13.  */
  14.  
  15. static char sccsid[] = "@(#) tkTextBTree.c 1.25 95/01/03 17:06:15";
  16.  
  17. #include "tkInt.h"
  18. #include "tkPort.h"
  19. #include "tkText.h"
  20.  
  21. /*
  22.  * The data structure below keeps summary information about one tag as part
  23.  * of the tag information in a node.
  24.  */
  25.  
  26. typedef struct Summary {
  27.     TkTextTag *tagPtr;            /* Handle for tag. */
  28.     int toggleCount;            /* Number of transitions into or
  29.                      * out of this tag that occur in
  30.                      * the subtree rooted at this node. */
  31.     struct Summary *nextPtr;        /* Next in list of all tags for same
  32.                      * node, or NULL if at end of list. */
  33. } Summary;
  34.  
  35. /*
  36.  * The data structure below defines a node in the B-tree.
  37.  */
  38.  
  39. typedef struct Node {
  40.     struct Node *parentPtr;        /* Pointer to parent node, or NULL if
  41.                      * this is the root. */
  42.     struct Node *nextPtr;        /* Next in list of siblings with the
  43.                      * same parent node, or NULL for end
  44.                      * of list. */
  45.     Summary *summaryPtr;        /* First in malloc-ed list of info
  46.                      * about tags in this subtree (NULL if
  47.                      * no tag info in the subtree). */
  48.     int level;                /* Level of this node in the B-tree.
  49.                      * 0 refers to the bottom of the tree
  50.                      * (children are lines, not nodes). */
  51.     union {                /* First in linked list of children. */
  52.     struct Node *nodePtr;        /* Used if level > 0. */
  53.     TkTextLine *linePtr;        /* Used if level == 0. */
  54.     } children;
  55.     int numChildren;            /* Number of children of this node. */
  56.     int numLines;            /* Total number of lines (leaves) in
  57.                      * the subtree rooted here. */
  58. } Node;
  59.  
  60. /*
  61.  * Upper and lower bounds on how many children a node may have:
  62.  * rebalance when either of these limits is exceeded.  MAX_CHILDREN
  63.  * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
  64.  */
  65.  
  66. #define MAX_CHILDREN 12
  67. #define MIN_CHILDREN 6
  68.  
  69. /*
  70.  * The data structure below defines an entire B-tree.
  71.  */
  72.  
  73. typedef struct BTree {
  74.     Node *rootPtr;            /* Pointer to root of B-tree. */
  75. } BTree;
  76.  
  77. /*
  78.  * The structure below is used to pass information between
  79.  * TkBTreeGetTags and IncCount:
  80.  */
  81.  
  82. typedef struct TagInfo {
  83.     int numTags;            /* Number of tags for which there
  84.                      * is currently information in
  85.                      * tags and counts. */
  86.     int arraySize;            /* Number of entries allocated for
  87.                      * tags and counts. */
  88.     TkTextTag **tagPtrs;        /* Array of tags seen so far.
  89.                      * Malloc-ed. */
  90.     int *counts;            /* Toggle count (so far) for each
  91.                      * entry in tags.  Malloc-ed. */
  92. } TagInfo;
  93.  
  94. /*
  95.  * Variable that indicates whether to enable consistency checks for
  96.  * debugging.
  97.  */
  98.  
  99. int tkBTreeDebug = 0;
  100.  
  101. /*
  102.  * Macros that determine how much space to allocate for new segments:
  103.  */
  104.  
  105. #define CSEG_SIZE(chars) ((unsigned) (Tk_Offset(TkTextSegment, body) \
  106.     + 1 + (chars)))
  107. #define TSEG_SIZE ((unsigned) (Tk_Offset(TkTextSegment, body) \
  108.     + sizeof(TkTextToggle)))
  109.  
  110. /*
  111.  * Forward declarations for procedures defined in this file:
  112.  */
  113.  
  114. static void        ChangeNodeToggleCount _ANSI_ARGS_((Node *nodePtr,
  115.                 TkTextTag *tagPtr, int delta));
  116. static void        CharCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
  117.                 TkTextLine *linePtr));
  118. static int        CharDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
  119.                 TkTextLine *linePtr, int treeGone));
  120. static TkTextSegment *    CharCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
  121.                 TkTextLine *linePtr));
  122. static TkTextSegment *    CharSplitProc _ANSI_ARGS_((TkTextSegment *segPtr,
  123.                 int index));
  124. static void        CheckNodeConsistency _ANSI_ARGS_((Node *nodePtr));
  125. static void        CleanupLine _ANSI_ARGS_((TkTextLine *linePtr));
  126. static void        DeleteSummaries _ANSI_ARGS_((Summary *tagPtr));
  127. static void        DestroyNode _ANSI_ARGS_((Node *nodePtr));
  128. static void        IncCount _ANSI_ARGS_((TkTextTag *tagPtr, int inc,
  129.                 TagInfo *tagInfoPtr));
  130. static void        Rebalance _ANSI_ARGS_((BTree *treePtr, Node *nodePtr));
  131. static void        RecomputeNodeCounts _ANSI_ARGS_((Node *nodePtr));
  132. static TkTextSegment *    SplitSeg _ANSI_ARGS_((TkTextIndex *indexPtr));
  133. static void        ToggleCheckProc _ANSI_ARGS_((TkTextSegment *segPtr,
  134.                 TkTextLine *linePtr));
  135. static TkTextSegment *    ToggleCleanupProc _ANSI_ARGS_((TkTextSegment *segPtr,
  136.                 TkTextLine *linePtr));
  137. static int        ToggleDeleteProc _ANSI_ARGS_((TkTextSegment *segPtr,
  138.                 TkTextLine *linePtr, int treeGone));
  139. static void        ToggleLineChangeProc _ANSI_ARGS_((TkTextSegment *segPtr,
  140.                 TkTextLine *linePtr));
  141.  
  142. /*
  143.  * Type record for character segments:
  144.  */
  145.  
  146. Tk_SegType tkTextCharType = {
  147.     "character",                /* name */
  148.     0,                        /* leftGravity */
  149.     CharSplitProc,                /* splitProc */
  150.     CharDeleteProc,                /* deleteProc */
  151.     CharCleanupProc,                /* cleanupProc */
  152.     (Tk_SegLineChangeProc *) NULL,        /* lineChangeProc */
  153.     TkTextCharLayoutProc,            /* layoutProc */
  154.     CharCheckProc                /* checkProc */
  155. };
  156.  
  157. /*
  158.  * Type record for segments marking the beginning of a tagged
  159.  * range:
  160.  */
  161.  
  162. Tk_SegType tkTextToggleOnType = {
  163.     "toggleOn",                    /* name */
  164.     0,                        /* leftGravity */
  165.     (Tk_SegSplitProc *) NULL,            /* splitProc */
  166.     ToggleDeleteProc,                /* deleteProc */
  167.     ToggleCleanupProc,                /* cleanupProc */
  168.     ToggleLineChangeProc,            /* lineChangeProc */
  169.     (Tk_SegLayoutProc *) NULL,            /* layoutProc */
  170.     ToggleCheckProc                /* checkProc */
  171. };
  172.  
  173. /*
  174.  * Type record for segments marking the end of a tagged
  175.  * range:
  176.  */
  177.  
  178. Tk_SegType tkTextToggleOffType = {
  179.     "toggleOff",                /* name */
  180.     1,                        /* leftGravity */
  181.     (Tk_SegSplitProc *) NULL,            /* splitProc */
  182.     ToggleDeleteProc,                /* deleteProc */
  183.     ToggleCleanupProc,                /* cleanupProc */
  184.     ToggleLineChangeProc,            /* lineChangeProc */
  185.     (Tk_SegLayoutProc *) NULL,            /* layoutProc */
  186.     ToggleCheckProc                /* checkProc */
  187. };
  188.  
  189. /*
  190.  *----------------------------------------------------------------------
  191.  *
  192.  * TkBTreeCreate --
  193.  *
  194.  *    This procedure is called to create a new text B-tree.
  195.  *
  196.  * Results:
  197.  *    The return value is a pointer to a new B-tree containing
  198.  *    one line with nothing but a newline character.
  199.  *
  200.  * Side effects:
  201.  *    Memory is allocated and initialized.
  202.  *
  203.  *----------------------------------------------------------------------
  204.  */
  205.  
  206. TkTextBTree
  207. TkBTreeCreate()
  208. {
  209.     register BTree *treePtr;
  210.     register Node *rootPtr;
  211.     register TkTextLine *linePtr, *linePtr2;
  212.     register TkTextSegment *segPtr;
  213.  
  214.     /*
  215.      * The tree will initially have two empty lines.  The second line
  216.      * isn't actually part of the tree's contents, but its presence
  217.      * makes several operations easier.  The tree will have one node,
  218.      * which is also the root of the tree.
  219.      */
  220.  
  221.     rootPtr = (Node *) ckalloc(sizeof(Node));
  222.     linePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
  223.     linePtr2 = (TkTextLine *) ckalloc(sizeof(TkTextLine));
  224.     rootPtr->parentPtr = NULL;
  225.     rootPtr->nextPtr = NULL;
  226.     rootPtr->summaryPtr = NULL;
  227.     rootPtr->level = 0;
  228.     rootPtr->children.linePtr = linePtr;
  229.     rootPtr->numChildren = 2;
  230.     rootPtr->numLines = 2;
  231.  
  232.     linePtr->parentPtr = rootPtr;
  233.     linePtr->nextPtr = linePtr2;
  234.     segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
  235.     linePtr->segPtr = segPtr;
  236.     segPtr->typePtr = &tkTextCharType;
  237.     segPtr->nextPtr = NULL;
  238.     segPtr->size = 1;
  239.     segPtr->body.chars[0] = '\n';
  240.     segPtr->body.chars[1] = 0;
  241.  
  242.     linePtr2->parentPtr = rootPtr;
  243.     linePtr2->nextPtr = NULL;
  244.     segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(1));
  245.     linePtr2->segPtr = segPtr;
  246.     segPtr->typePtr = &tkTextCharType;
  247.     segPtr->nextPtr = NULL;
  248.     segPtr->size = 1;
  249.     segPtr->body.chars[0] = '\n';
  250.     segPtr->body.chars[1] = 0;
  251.  
  252.     treePtr = (BTree *) ckalloc(sizeof(BTree));
  253.     treePtr->rootPtr = rootPtr;
  254.  
  255.     return (TkTextBTree) treePtr;
  256. }
  257.  
  258. /*
  259.  *----------------------------------------------------------------------
  260.  *
  261.  * TkBTreeDestroy --
  262.  *
  263.  *    Delete a B-tree, recycling all of the storage it contains.
  264.  *
  265.  * Results:
  266.  *    The tree given by treePtr is deleted.  TreePtr should never
  267.  *    again be used.
  268.  *
  269.  * Side effects:
  270.  *    Memory is freed.
  271.  *
  272.  *----------------------------------------------------------------------
  273.  */
  274.  
  275. void
  276. TkBTreeDestroy(tree)
  277.     TkTextBTree tree;            /* Pointer to tree to delete. */ 
  278. {
  279.     BTree *treePtr = (BTree *) tree;
  280.  
  281.     DestroyNode(treePtr->rootPtr);
  282.     ckfree((char *) treePtr);
  283. }
  284.  
  285. /*
  286.  *----------------------------------------------------------------------
  287.  *
  288.  * DestroyNode --
  289.  *
  290.  *    This is a recursive utility procedure used during the deletion
  291.  *    of a B-tree.
  292.  *
  293.  * Results:
  294.  *    None.
  295.  *
  296.  * Side effects:
  297.  *    All the storage for nodePtr and its descendants is freed.
  298.  *
  299.  *----------------------------------------------------------------------
  300.  */
  301.  
  302. static void
  303. DestroyNode(nodePtr)
  304.     register Node *nodePtr;
  305. {
  306.     if (nodePtr->level == 0) {
  307.     TkTextLine *linePtr;
  308.     TkTextSegment *segPtr;
  309.  
  310.     while (nodePtr->children.linePtr != NULL) {
  311.         linePtr = nodePtr->children.linePtr;
  312.         nodePtr->children.linePtr = linePtr->nextPtr;
  313.         while (linePtr->segPtr != NULL) {
  314.         segPtr = linePtr->segPtr;
  315.         linePtr->segPtr = segPtr->nextPtr;
  316.         (*segPtr->typePtr->deleteProc)(segPtr, linePtr, 1);
  317.         }
  318.         ckfree((char *) linePtr);
  319.     }
  320.     } else {
  321.     register Node *childPtr;
  322.  
  323.     while (nodePtr->children.nodePtr != NULL) {
  324.         childPtr = nodePtr->children.nodePtr;
  325.         nodePtr->children.nodePtr = childPtr->nextPtr;
  326.         DestroyNode(childPtr);
  327.     }
  328.     }
  329.     DeleteSummaries(nodePtr->summaryPtr);
  330.     ckfree((char *) nodePtr);
  331. }
  332.  
  333. /*
  334.  *----------------------------------------------------------------------
  335.  *
  336.  * DeleteSummaries --
  337.  *
  338.  *    Free up all of the memory in a list of tag summaries associated
  339.  *    with a node.
  340.  *
  341.  * Results:
  342.  *    None.
  343.  *
  344.  * Side effects:
  345.  *    Storage is released.
  346.  *
  347.  *----------------------------------------------------------------------
  348.  */
  349.  
  350. static void
  351. DeleteSummaries(summaryPtr)
  352.     register Summary *summaryPtr;    /* First in list of node's tag
  353.                      * summaries. */
  354. {
  355.     register Summary *nextPtr;
  356.     while (summaryPtr != NULL) {
  357.     nextPtr = summaryPtr->nextPtr;
  358.     ckfree((char *) summaryPtr);
  359.     summaryPtr = nextPtr;
  360.     }
  361. }
  362.  
  363. /*
  364.  *----------------------------------------------------------------------
  365.  *
  366.  * TkBTreeInsertChars --
  367.  *
  368.  *    Insert characters at a given position in a B-tree.
  369.  *
  370.  * Results:
  371.  *    None.
  372.  *
  373.  * Side effects:
  374.  *    Characters are added to the B-tree at the given position.
  375.  *    If the string contains newlines, new lines will be added,
  376.  *    which could cause the structure of the B-tree to change.
  377.  *
  378.  *----------------------------------------------------------------------
  379.  */
  380.  
  381. void
  382. TkBTreeInsertChars(indexPtr, string)
  383.     register TkTextIndex *indexPtr;    /* Indicates where to insert text.
  384.                      * When the procedure returns, this
  385.                      * index is no longer valid because
  386.                      * of changes to the segment
  387.                      * structure. */
  388.     char *string;            /* Pointer to bytes to insert (may
  389.                      * contain newlines, must be null-
  390.                      * terminated). */
  391. {
  392.     register Node *nodePtr;
  393.     register TkTextSegment *prevPtr;    /* The segment just before the first
  394.                      * new segment (NULL means new segment
  395.                      * is at beginning of line). */
  396.     TkTextSegment *curPtr;        /* Current segment;  new characters
  397.                      * are inserted just after this one. 
  398.                      * NULL means insert at beginning of
  399.                      * line. */
  400.     TkTextLine *linePtr;        /* Current line (new segments are
  401.                      * added to this line). */
  402.     register TkTextSegment *segPtr;
  403.     TkTextLine *newLinePtr;
  404.     int chunkSize;            /* # characters in current chunk. */
  405.     register char *eol;            /* Pointer to character just after last
  406.                      * one in current chunk. */
  407.     int changeToLineCount;        /* Counts change to total number of
  408.                      * lines in file. */
  409.  
  410.     prevPtr = SplitSeg(indexPtr);
  411.     linePtr = indexPtr->linePtr;
  412.     curPtr = prevPtr;
  413.  
  414.     /*
  415.      * Chop the string up into lines and create a new segment for
  416.      * each line, plus a new line for the leftovers from the
  417.      * previous line.
  418.      */
  419.  
  420.     changeToLineCount = 0;
  421.     while (*string != 0) {
  422.     for (eol = string; *eol != 0; eol++) {
  423.         if (*eol == '\n') {
  424.         eol++;
  425.         break;
  426.         }
  427.     }
  428.     chunkSize = eol-string;
  429.     segPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(chunkSize));
  430.     segPtr->typePtr = &tkTextCharType;
  431.     if (curPtr == NULL) {
  432.         segPtr->nextPtr = linePtr->segPtr;
  433.         linePtr->segPtr = segPtr;
  434.     } else {
  435.         segPtr->nextPtr = curPtr->nextPtr;
  436.         curPtr->nextPtr = segPtr;
  437.     }
  438.     segPtr->size = chunkSize;
  439.     strncpy(segPtr->body.chars, string, (size_t) chunkSize);
  440.     segPtr->body.chars[chunkSize] = 0;
  441.     curPtr = segPtr;
  442.  
  443.     if (eol[-1] != '\n') {
  444.         break;
  445.     }
  446.  
  447.     /*
  448.      * The chunk ended with a newline, so create a new TkTextLine
  449.      * and move the remainder of the old line to it.
  450.      */
  451.  
  452.     newLinePtr = (TkTextLine *) ckalloc(sizeof(TkTextLine));
  453.     newLinePtr->parentPtr = linePtr->parentPtr;
  454.     newLinePtr->nextPtr = linePtr->nextPtr;
  455.     linePtr->nextPtr = newLinePtr;
  456.     newLinePtr->segPtr = segPtr->nextPtr;
  457.     segPtr->nextPtr = NULL;
  458.     linePtr = newLinePtr;
  459.     curPtr = NULL;
  460.     changeToLineCount++;
  461.  
  462.     string = eol;
  463.     }
  464.  
  465.     /*
  466.      * Cleanup the starting line for the insertion, plus the ending
  467.      * line if it's different.
  468.      */
  469.  
  470.     CleanupLine(indexPtr->linePtr);
  471.     if (linePtr != indexPtr->linePtr) {
  472.     CleanupLine(linePtr);
  473.     }
  474.  
  475.     /*
  476.      * Increment the line counts in all the parent nodes of the insertion
  477.      * point, then rebalance the tree if necessary.
  478.      */
  479.  
  480.     for (nodePtr = linePtr->parentPtr ; nodePtr != NULL;
  481.         nodePtr = nodePtr->parentPtr) {
  482.     nodePtr->numLines += changeToLineCount;
  483.     }
  484.     nodePtr = linePtr->parentPtr;
  485.     nodePtr->numChildren += changeToLineCount;
  486.     if (nodePtr->numChildren > MAX_CHILDREN) {
  487.     Rebalance((BTree *) indexPtr->tree, nodePtr);
  488.     }
  489.  
  490.     if (tkBTreeDebug) {
  491.     TkBTreeCheck(indexPtr->tree);
  492.     }
  493. }
  494.  
  495. /*
  496.  *--------------------------------------------------------------
  497.  *
  498.  * SplitSeg --
  499.  *
  500.  *    This procedure is called before adding or deleting
  501.  *    segments.  It does three things: (a) it finds the segment
  502.  *    containing indexPtr;  (b) if there are several such
  503.  *    segments (because some segments have zero length) then
  504.  *    it picks the first segment that does not have left
  505.  *    gravity;  (c) if the index refers to the middle of
  506.  *    a segment then it splits the segment so that the
  507.  *    index now refers to the beginning of a segment.
  508.  *
  509.  * Results:
  510.  *    The return value is a pointer to the segment just
  511.  *    before the segment corresponding to indexPtr (as
  512.  *    described above).  If the segment corresponding to
  513.  *    indexPtr is the first in its line then the return
  514.  *    value is NULL.
  515.  *
  516.  * Side effects:
  517.  *    The segment referred to by indexPtr is split unless
  518.  *    indexPtr refers to its first character.
  519.  *
  520.  *--------------------------------------------------------------
  521.  */
  522.  
  523. static TkTextSegment *
  524. SplitSeg(indexPtr)
  525.     TkTextIndex *indexPtr;        /* Index identifying position
  526.                      * at which to split a segment. */
  527. {
  528.     TkTextSegment *prevPtr, *segPtr;
  529.     int count;
  530.  
  531.     for (count = indexPtr->charIndex, prevPtr = NULL,
  532.         segPtr = indexPtr->linePtr->segPtr; segPtr != NULL;
  533.         count -= segPtr->size, prevPtr = segPtr, segPtr = segPtr->nextPtr) {
  534.     if (segPtr->size > count) {
  535.         if (count == 0) {
  536.         return prevPtr;
  537.         }
  538.         segPtr = (*segPtr->typePtr->splitProc)(segPtr, count);
  539.         if (prevPtr == NULL) {
  540.         indexPtr->linePtr->segPtr = segPtr;
  541.         } else {
  542.         prevPtr->nextPtr = segPtr;
  543.         }
  544.         return segPtr;
  545.     } else if ((segPtr->size == 0) && (count == 0)
  546.         && !segPtr->typePtr->leftGravity) {
  547.         return prevPtr;
  548.     }
  549.     }
  550.     panic("SplitSeg reached end of line!");
  551.     return NULL;
  552. }
  553.  
  554. /*
  555.  *--------------------------------------------------------------
  556.  *
  557.  * CleanupLine --
  558.  *
  559.  *    This procedure is called after modifications have been
  560.  *    made to a line.  It scans over all of the segments in
  561.  *    the line, giving each a chance to clean itself up, e.g.
  562.  *    by merging with the following segments, updating internal
  563.  *    information, etc.
  564.  *
  565.  * Results:
  566.  *    None.
  567.  *
  568.  * Side effects:
  569.  *    Depends on what the segment-specific cleanup procedures do.
  570.  *
  571.  *--------------------------------------------------------------
  572.  */
  573.  
  574. static void
  575. CleanupLine(linePtr)
  576.     TkTextLine *linePtr;        /* Line to be cleaned up. */
  577. {
  578.     TkTextSegment *segPtr, **prevPtrPtr;
  579.     int anyChanges;
  580.  
  581.     /*
  582.      * Make a pass over all of the segments in the line, giving each
  583.      * a chance to clean itself up.  This could potentially change
  584.      * the structure of the line, e.g. by merging two segments
  585.      * together or having two segments cancel themselves;  if so,
  586.      * then repeat the whole process again, since the first structure
  587.      * change might make other structure changes possible.  Repeat
  588.      * until eventually there are no changes.
  589.      */
  590.  
  591.     while (1) {
  592.     anyChanges = 0;
  593.     for (prevPtrPtr = &linePtr->segPtr, segPtr = *prevPtrPtr;
  594.         segPtr != NULL;
  595.         prevPtrPtr = &(*prevPtrPtr)->nextPtr, segPtr = *prevPtrPtr) {
  596.         if (segPtr->typePtr->cleanupProc != NULL) {
  597.         *prevPtrPtr = (*segPtr->typePtr->cleanupProc)(segPtr, linePtr);
  598.         if (segPtr != *prevPtrPtr) {
  599.             anyChanges = 1;
  600.         }
  601.         }
  602.     }
  603.     if (!anyChanges) {
  604.         break;
  605.     }
  606.     }
  607. }
  608.  
  609. /*
  610.  *----------------------------------------------------------------------
  611.  *
  612.  * TkBTreeDeleteChars --
  613.  *
  614.  *    Delete a range of characters from a B-tree.  The caller
  615.  *    must make sure that the final newline of the B-tree is
  616.  *    never deleted.
  617.  *
  618.  * Results:
  619.  *    None.
  620.  *
  621.  * Side effects:
  622.  *    Information is deleted from the B-tree.  This can cause the
  623.  *    internal structure of the B-tree to change.  Note: because
  624.  *    of changes to the B-tree structure, the indices pointed
  625.  *    to by index1Ptr and index2Ptr should not be used after this
  626.  *    procedure returns.
  627.  *
  628.  *----------------------------------------------------------------------
  629.  */
  630.  
  631. void
  632. TkBTreeDeleteChars(index1Ptr, index2Ptr)
  633.     register TkTextIndex *index1Ptr;    /* Indicates first character that is
  634.                      * to be deleted. */
  635.     register TkTextIndex *index2Ptr;    /* Indicates character just after the
  636.                      * last one that is to be deleted. */
  637. {
  638.     TkTextSegment *prevPtr;        /* The segment just before the start
  639.                      * of the deletion range. */
  640.     TkTextSegment *lastPtr;        /* The segment just after the end
  641.                      * of the deletion range. */
  642.     TkTextSegment *segPtr, *nextPtr;
  643.     TkTextLine *curLinePtr;
  644.     Node *curNodePtr, *nodePtr;
  645.  
  646.     /*
  647.      * Tricky point:  split at index2Ptr first;  otherwise the split
  648.      * at index2Ptr may invalidate segPtr and/or prevPtr.
  649.      */
  650.  
  651.     lastPtr = SplitSeg(index2Ptr);
  652.     if (lastPtr != NULL) {
  653.     lastPtr = lastPtr->nextPtr;
  654.     }  else {
  655.     lastPtr = index2Ptr->linePtr->segPtr;
  656.     }
  657.     prevPtr = SplitSeg(index1Ptr);
  658.     if (prevPtr != NULL) {
  659.     segPtr = prevPtr->nextPtr;
  660.     prevPtr->nextPtr = lastPtr;
  661.     } else {
  662.     segPtr = index1Ptr->linePtr->segPtr;
  663.     index1Ptr->linePtr->segPtr = lastPtr;
  664.     }
  665.  
  666.     /*
  667.      * Delete all of the segments between prevPtr and lastPtr.
  668.      */
  669.  
  670.     curLinePtr = index1Ptr->linePtr;
  671.     curNodePtr = curLinePtr->parentPtr;
  672.     while (segPtr != lastPtr) {
  673.     if (segPtr == NULL) {
  674.         TkTextLine *nextLinePtr;
  675.  
  676.         /*
  677.          * We just ran off the end of a line.  First find the
  678.          * next line, then go back to the old line and delete it
  679.          * (unless it's the starting line for the range).
  680.          */
  681.  
  682.         nextLinePtr = TkBTreeNextLine(curLinePtr);
  683.         if (curLinePtr != index1Ptr->linePtr) {
  684.         if (curNodePtr == index1Ptr->linePtr->parentPtr) {
  685.             index1Ptr->linePtr->nextPtr = curLinePtr->nextPtr;
  686.         } else {
  687.             curNodePtr->children.linePtr = curLinePtr->nextPtr;
  688.         }
  689.         for (nodePtr = curNodePtr; nodePtr != NULL;
  690.             nodePtr = nodePtr->parentPtr) {
  691.             nodePtr->numLines--;
  692.         }
  693.         curNodePtr->numChildren--;
  694.         ckfree((char *) curLinePtr);
  695.         }
  696.         curLinePtr = nextLinePtr;
  697.         segPtr = curLinePtr->segPtr;
  698.  
  699.         /*
  700.          * If the node is empty then delete it and its parents,
  701.          * recursively upwards until a non-empty node is found.
  702.          */
  703.  
  704.         while (curNodePtr->numChildren == 0) {
  705.         Node *parentPtr;
  706.  
  707.         parentPtr = curNodePtr->parentPtr;
  708.         if (parentPtr->children.nodePtr == curNodePtr) {
  709.             parentPtr->children.nodePtr = curNodePtr->nextPtr;
  710.         } else {
  711.             Node *prevNodePtr = parentPtr->children.nodePtr;
  712.             while (prevNodePtr->nextPtr != curNodePtr) {
  713.             prevNodePtr = prevNodePtr->nextPtr;
  714.             }
  715.             prevNodePtr->nextPtr = curNodePtr->nextPtr;
  716.         }
  717.         parentPtr->numChildren--;
  718.         DeleteSummaries(curNodePtr->summaryPtr);
  719.         ckfree((char *) curNodePtr);
  720.         curNodePtr = parentPtr;
  721.         }
  722.         curNodePtr = curLinePtr->parentPtr;
  723.         continue;
  724.     }
  725.  
  726.     nextPtr = segPtr->nextPtr;
  727.     if ((*segPtr->typePtr->deleteProc)(segPtr, curLinePtr, 0) != 0) {
  728.         /*
  729.          * This segment refuses to die.  Move it to prevPtr and
  730.          * advance prevPtr if the segment has left gravity.
  731.          */
  732.  
  733.         if (prevPtr == NULL) {
  734.         segPtr->nextPtr = index1Ptr->linePtr->segPtr;
  735.         index1Ptr->linePtr->segPtr = segPtr;
  736.         } else {
  737.         segPtr->nextPtr = prevPtr->nextPtr;
  738.         prevPtr->nextPtr = segPtr;
  739.         }
  740.         if (segPtr->typePtr->leftGravity) {
  741.         prevPtr = segPtr;
  742.         }
  743.     }
  744.     segPtr = nextPtr;
  745.     }
  746.  
  747.     /*
  748.      * If the beginning and end of the deletion range are in different
  749.      * lines, join the two lines together and discard the ending line.
  750.      */
  751.  
  752.     if (index1Ptr->linePtr != index2Ptr->linePtr) {
  753.     TkTextLine *prevLinePtr;
  754.  
  755.     for (segPtr = lastPtr; segPtr != NULL;
  756.         segPtr = segPtr->nextPtr) {
  757.         if (segPtr->typePtr->lineChangeProc != NULL) {
  758.         (*segPtr->typePtr->lineChangeProc)(segPtr, index2Ptr->linePtr);
  759.         }
  760.     }
  761.     curNodePtr = index2Ptr->linePtr->parentPtr;
  762.     for (nodePtr = curNodePtr; nodePtr != NULL;
  763.         nodePtr = nodePtr->parentPtr) {
  764.         nodePtr->numLines--;
  765.     }
  766.     curNodePtr->numChildren--;
  767.     prevLinePtr = curNodePtr->children.linePtr;
  768.     if (prevLinePtr == index2Ptr->linePtr) {
  769.         curNodePtr->children.linePtr = index2Ptr->linePtr->nextPtr;
  770.     } else {
  771.         while (prevLinePtr->nextPtr != index2Ptr->linePtr) {
  772.         prevLinePtr = prevLinePtr->nextPtr;
  773.         }
  774.         prevLinePtr->nextPtr = index2Ptr->linePtr->nextPtr;
  775.     }
  776.     ckfree((char *) index2Ptr->linePtr);
  777.     Rebalance((BTree *) index2Ptr->tree, curNodePtr);
  778.     }
  779.  
  780.     /*
  781.      * Cleanup the segments in the new line.
  782.      */
  783.  
  784.     CleanupLine(index1Ptr->linePtr);
  785.  
  786.     /*
  787.      * Lastly, rebalance the first node of the range.
  788.      */
  789.  
  790.     Rebalance((BTree *) index1Ptr->tree, index1Ptr->linePtr->parentPtr);
  791.     if (tkBTreeDebug) {
  792.     TkBTreeCheck(index1Ptr->tree);
  793.     }
  794. }
  795.  
  796. /*
  797.  *----------------------------------------------------------------------
  798.  *
  799.  * TkBTreeFindLine --
  800.  *
  801.  *    Find a particular line in a B-tree based on its line number.
  802.  *
  803.  * Results:
  804.  *    The return value is a pointer to the line structure for the
  805.  *    line whose index is "line", or NULL if no such line exists.
  806.  *
  807.  * Side effects:
  808.  *    None.
  809.  *
  810.  *----------------------------------------------------------------------
  811.  */
  812.  
  813. TkTextLine *
  814. TkBTreeFindLine(tree, line)
  815.     TkTextBTree tree;            /* B-tree in which to find line. */
  816.     int line;                /* Index of desired line. */
  817. {
  818.     BTree *treePtr = (BTree *) tree;
  819.     register Node *nodePtr;
  820.     register TkTextLine *linePtr;
  821.     int linesLeft;
  822.  
  823.     nodePtr = treePtr->rootPtr;
  824.     linesLeft = line;
  825.     if ((line < 0) || (line >= nodePtr->numLines)) {
  826.     return NULL;
  827.     }
  828.  
  829.     /*
  830.      * Work down through levels of the tree until a node is found at
  831.      * level 0.
  832.      */
  833.  
  834.     while (nodePtr->level != 0) {
  835.     for (nodePtr = nodePtr->children.nodePtr;
  836.         nodePtr->numLines <= linesLeft;
  837.         nodePtr = nodePtr->nextPtr) {
  838.         if (nodePtr == NULL) {
  839.         panic("TkBTreeFindLine ran out of nodes");
  840.         }
  841.         linesLeft -= nodePtr->numLines;
  842.     }
  843.     }
  844.  
  845.     /*
  846.      * Work through the lines attached to the level-0 node.
  847.      */
  848.  
  849.     for (linePtr = nodePtr->children.linePtr; linesLeft > 0;
  850.         linePtr = linePtr->nextPtr) {
  851.     if (linePtr == NULL) {
  852.         panic("TkBTreeFindLine ran out of lines");
  853.     }
  854.     linesLeft -= 1;
  855.     }
  856.     return linePtr;
  857. }
  858.  
  859. /*
  860.  *----------------------------------------------------------------------
  861.  *
  862.  * TkBTreeNextLine --
  863.  *
  864.  *    Given an existing line in a B-tree, this procedure locates the
  865.  *    next line in the B-tree.  This procedure is used for scanning
  866.  *    through the B-tree.
  867.  *
  868.  * Results:
  869.  *    The return value is a pointer to the line that immediately
  870.  *    follows linePtr, or NULL if there is no such line.
  871.  *
  872.  * Side effects:
  873.  *    None.
  874.  *
  875.  *----------------------------------------------------------------------
  876.  */
  877.  
  878. TkTextLine *
  879. TkBTreeNextLine(linePtr)
  880.     register TkTextLine *linePtr;    /* Pointer to existing line in
  881.                      * B-tree. */
  882. {
  883.     register Node *nodePtr;
  884.  
  885.     if (linePtr->nextPtr != NULL) {
  886.     return linePtr->nextPtr;
  887.     }
  888.  
  889.     /*
  890.      * This was the last line associated with the particular parent node.
  891.      * Search up the tree for the next node, then search down from that
  892.      * node to find the first line,
  893.      */
  894.  
  895.     for (nodePtr = linePtr->parentPtr; ; nodePtr = nodePtr->parentPtr) {
  896.     if (nodePtr->nextPtr != NULL) {
  897.         nodePtr = nodePtr->nextPtr;
  898.         break;
  899.     }
  900.     if (nodePtr->parentPtr == NULL) {
  901.         return (TkTextLine *) NULL;
  902.     }
  903.     }
  904.     while (nodePtr->level > 0) {
  905.     nodePtr = nodePtr->children.nodePtr;
  906.     }
  907.     return nodePtr->children.linePtr;
  908. }
  909.  
  910. /*
  911.  *----------------------------------------------------------------------
  912.  *
  913.  * TkBTreeLineIndex --
  914.  *
  915.  *    Given a pointer to a line in a B-tree, return the numerical
  916.  *    index of that line.
  917.  *
  918.  * Results:
  919.  *    The result is the index of linePtr within the tree, where 0
  920.  *    corresponds to the first line in the tree.
  921.  *
  922.  * Side effects:
  923.  *    None.
  924.  *
  925.  *----------------------------------------------------------------------
  926.  */
  927.  
  928. int
  929. TkBTreeLineIndex(linePtr)
  930.     TkTextLine *linePtr;        /* Pointer to existing line in
  931.                      * B-tree. */
  932. {
  933.     register TkTextLine *linePtr2;
  934.     register Node *nodePtr, *parentPtr, *nodePtr2;
  935.     int index;
  936.  
  937.     /*
  938.      * First count how many lines precede this one in its level-0
  939.      * node.
  940.      */
  941.  
  942.     nodePtr = linePtr->parentPtr;
  943.     index = 0;
  944.     for (linePtr2 = nodePtr->children.linePtr; linePtr2 != linePtr;
  945.         linePtr2 = linePtr2->nextPtr) {
  946.     if (linePtr2 == NULL) {
  947.         panic("TkBTreeLineIndex couldn't find line");
  948.     }
  949.     index += 1;
  950.     }
  951.  
  952.     /*
  953.      * Now work up through the levels of the tree one at a time,
  954.      * counting how many lines are in nodes preceding the current
  955.      * node.
  956.      */
  957.  
  958.     for (parentPtr = nodePtr->parentPtr ; parentPtr != NULL;
  959.         nodePtr = parentPtr, parentPtr = parentPtr->parentPtr) {
  960.     for (nodePtr2 = parentPtr->children.nodePtr; nodePtr2 != nodePtr;
  961.         nodePtr2 = nodePtr2->nextPtr) {
  962.         if (nodePtr2 == NULL) {
  963.         panic("TkBTreeLineIndex couldn't find node");
  964.         }
  965.         index += nodePtr2->numLines;
  966.     }
  967.     }
  968.     return index;
  969. }
  970.  
  971. /*
  972.  *----------------------------------------------------------------------
  973.  *
  974.  * TkBTreeLinkSegment --
  975.  *
  976.  *    This procedure adds a new segment to a B-tree at a given
  977.  *    location.
  978.  *
  979.  * Results:
  980.  *    None.
  981.  *
  982.  * Side effects:
  983.  *    SegPtr will be linked into its tree.
  984.  *
  985.  *----------------------------------------------------------------------
  986.  */
  987.  
  988.     /* ARGSUSED */
  989. void
  990. TkBTreeLinkSegment(segPtr, indexPtr)
  991.     TkTextSegment *segPtr;    /* Pointer to new segment to be added to
  992.                  * B-tree.  Should be completely initialized
  993.                  * by caller except for nextPtr field. */
  994.     TkTextIndex *indexPtr;    /* Where to add segment:  it gets linked
  995.                  * in just before the segment indicated
  996.                  * here. */
  997. {
  998.     register TkTextSegment *prevPtr;
  999.  
  1000.     prevPtr = SplitSeg(indexPtr);
  1001.     if (prevPtr == NULL) {
  1002.     segPtr->nextPtr = indexPtr->linePtr->segPtr;
  1003.     indexPtr->linePtr->segPtr = segPtr;
  1004.     } else {
  1005.     segPtr->nextPtr = prevPtr->nextPtr;
  1006.     prevPtr->nextPtr = segPtr;
  1007.     }
  1008.     CleanupLine(indexPtr->linePtr);
  1009.     if (tkBTreeDebug) {
  1010.     TkBTreeCheck(indexPtr->tree);
  1011.     }
  1012. }
  1013.  
  1014. /*
  1015.  *----------------------------------------------------------------------
  1016.  *
  1017.  * TkBTreeUnlinkSegment --
  1018.  *
  1019.  *    This procedure unlinks a segment from its line in a B-tree.
  1020.  *
  1021.  * Results:
  1022.  *    None.
  1023.  *
  1024.  * Side effects:
  1025.  *    SegPtr will be unlinked from linePtr.  The segment itself
  1026.  *    isn't modified by this procedure.
  1027.  *
  1028.  *----------------------------------------------------------------------
  1029.  */
  1030.  
  1031.     /* ARGSUSED */
  1032. void
  1033. TkBTreeUnlinkSegment(tree, segPtr, linePtr)
  1034.     TkTextBTree tree;            /* Tree containing segment. */
  1035.     TkTextSegment *segPtr;        /* Segment to be unlinked. */
  1036.     TkTextLine *linePtr;        /* Line that currently contains
  1037.                      * segment. */
  1038. {
  1039.     register TkTextSegment *prevPtr;
  1040.  
  1041.     if (linePtr->segPtr == segPtr) {
  1042.     linePtr->segPtr = segPtr->nextPtr;
  1043.     } else {
  1044.     for (prevPtr = linePtr->segPtr; prevPtr->nextPtr != segPtr;
  1045.         prevPtr = prevPtr->nextPtr) {
  1046.         /* Empty loop body. */
  1047.     }
  1048.     prevPtr->nextPtr = segPtr->nextPtr;
  1049.     }
  1050.     CleanupLine(linePtr);
  1051. }
  1052.  
  1053. /*
  1054.  *----------------------------------------------------------------------
  1055.  *
  1056.  * TkBTreeTag --
  1057.  *
  1058.  *    Turn a given tag on or off for a given range of characters in
  1059.  *    a B-tree of text.
  1060.  *
  1061.  * Results:
  1062.  *    None.
  1063.  *
  1064.  * Side effects:
  1065.  *    The given tag is added to the given range of characters
  1066.  *    in the tree or removed from all those characters, depending
  1067.  *    on the "add" argument.  The structure of the btree is modified
  1068.  *    enough that index1Ptr and index2Ptr are no longer valid after
  1069.  *    this procedure returns, and the indexes may be modified by
  1070.  *    this procedure.
  1071.  *
  1072.  *----------------------------------------------------------------------
  1073.  */
  1074.  
  1075. void
  1076. TkBTreeTag(index1Ptr, index2Ptr, tagPtr, add)
  1077.     register TkTextIndex *index1Ptr;    /* Indicates first character in
  1078.                      * range. */
  1079.     register TkTextIndex *index2Ptr;    /* Indicates character just after the
  1080.                      * last one in range. */
  1081.     TkTextTag *tagPtr;            /* Tag to add or remove. */
  1082.     int add;                /* One means add tag to the given
  1083.                      * range of characters;  zero means
  1084.                      * remove the tag from the range. */
  1085. {
  1086.     TkTextSegment *segPtr, *prevPtr;
  1087.     TkTextSearch search;
  1088.     TkTextLine *cleanupLinePtr;
  1089.     int oldState;
  1090.  
  1091.     /*
  1092.      * See whether the tag is present at the start of the range.  If
  1093.      * the state doesn't already match what we want then add a toggle
  1094.      * there.
  1095.      */
  1096.  
  1097.     oldState = TkBTreeCharTagged(index1Ptr, tagPtr);
  1098.     if ((add != 0) ^ oldState) {
  1099.     segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
  1100.     segPtr->typePtr = (add) ? &tkTextToggleOnType : &tkTextToggleOffType;
  1101.     prevPtr = SplitSeg(index1Ptr);
  1102.     if (prevPtr == NULL) {
  1103.         segPtr->nextPtr = index1Ptr->linePtr->segPtr;
  1104.         index1Ptr->linePtr->segPtr = segPtr;
  1105.     } else {
  1106.         segPtr->nextPtr = prevPtr->nextPtr;
  1107.         prevPtr->nextPtr = segPtr;
  1108.     }
  1109.     segPtr->size = 0;
  1110.     segPtr->body.toggle.tagPtr = tagPtr;
  1111.     segPtr->body.toggle.inNodeCounts = 0;
  1112.     }
  1113.  
  1114.     /*
  1115.      * Scan the range of characters and delete any internal tag
  1116.      * transitions.  Keep track of what the old state was at the end
  1117.      * of the range, and add a toggle there if it's needed.
  1118.      */
  1119.  
  1120.     TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, &search);
  1121.     cleanupLinePtr = index1Ptr->linePtr;
  1122.     while (TkBTreeNextTag(&search)) {
  1123.     oldState ^= 1;
  1124.     segPtr = search.segPtr;
  1125.     prevPtr = search.curIndex.linePtr->segPtr;
  1126.     if (prevPtr == segPtr) {
  1127.         search.curIndex.linePtr->segPtr = segPtr->nextPtr;
  1128.     } else {
  1129.         while (prevPtr->nextPtr != segPtr) {
  1130.         prevPtr = prevPtr->nextPtr;
  1131.         }
  1132.         prevPtr->nextPtr = segPtr->nextPtr;
  1133.     }
  1134.     if (segPtr->body.toggle.inNodeCounts) {
  1135.         ChangeNodeToggleCount(search.curIndex.linePtr->parentPtr,
  1136.             segPtr->body.toggle.tagPtr, -1);
  1137.         segPtr->body.toggle.inNodeCounts = 0;
  1138.     }
  1139.     ckfree((char *) segPtr);
  1140.  
  1141.     /*
  1142.      * The code below is a bit tricky.  After deleting a toggle
  1143.      * we eventually have to call CleanupLine, in order to allow
  1144.      * character segments to be merged together.  To do this, we
  1145.      * remember in cleanupLinePtr a line that needs to be
  1146.      * cleaned up, but we don't clean it up until we've moved
  1147.      * on to a different line.  That way the cleanup process
  1148.      * won't goof up segPtr.
  1149.      */
  1150.  
  1151.     if (cleanupLinePtr != search.curIndex.linePtr) {
  1152.         CleanupLine(cleanupLinePtr);
  1153.         cleanupLinePtr = search.curIndex.linePtr;
  1154.     }
  1155.     }
  1156.     if ((add != 0) ^ oldState) {
  1157.     segPtr = (TkTextSegment *) ckalloc(TSEG_SIZE);
  1158.     segPtr->typePtr = (add) ? &tkTextToggleOffType : &tkTextToggleOnType;
  1159.     prevPtr = SplitSeg(index2Ptr);
  1160.     if (prevPtr == NULL) {
  1161.         segPtr->nextPtr = index2Ptr->linePtr->segPtr;
  1162.         index2Ptr->linePtr->segPtr = segPtr;
  1163.     } else {
  1164.         segPtr->nextPtr = prevPtr->nextPtr;
  1165.         prevPtr->nextPtr = segPtr;
  1166.     }
  1167.     segPtr->size = 0;
  1168.     segPtr->body.toggle.tagPtr = tagPtr;
  1169.     segPtr->body.toggle.inNodeCounts = 0;
  1170.     }
  1171.  
  1172.     /*
  1173.      * Cleanup cleanupLinePtr and the last line of the range, if
  1174.      * these are different.
  1175.      */
  1176.  
  1177.     CleanupLine(cleanupLinePtr);
  1178.     if (cleanupLinePtr != index2Ptr->linePtr) {
  1179.     CleanupLine(index2Ptr->linePtr);
  1180.     }
  1181.  
  1182.     if (tkBTreeDebug) {
  1183.     TkBTreeCheck(index1Ptr->tree);
  1184.     }
  1185. }
  1186.  
  1187. /*
  1188.  *----------------------------------------------------------------------
  1189.  *
  1190.  * ChangeNodeToggleCount --
  1191.  *
  1192.  *    This procedure increments or decrements the toggle count for
  1193.  *    a particular tag in a particular node and all its ancestors.
  1194.  *
  1195.  * Results:
  1196.  *    None.
  1197.  *
  1198.  * Side effects:
  1199.  *    The toggle count for tag is adjusted up or down by "delta" in
  1200.  *    nodePtr.
  1201.  *
  1202.  *----------------------------------------------------------------------
  1203.  */
  1204.  
  1205. static void
  1206. ChangeNodeToggleCount(nodePtr, tagPtr, delta)
  1207.     register Node *nodePtr;        /* Node whose toggle count for a tag
  1208.                      * must be changed. */
  1209.     TkTextTag *tagPtr;            /* Information about tag. */
  1210.     int delta;                /* Amount to add to current toggle
  1211.                      * count for tag (may be negative). */
  1212. {
  1213.     register Summary *summaryPtr, *prevPtr;
  1214.  
  1215.     /*
  1216.      * Iterate over the node and all of its ancestors.
  1217.      */
  1218.  
  1219.     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
  1220.     /*
  1221.      * See if there's already an entry for this tag for this node.  If so,
  1222.      * perhaps all we have to do is adjust its count.
  1223.      */
  1224.     
  1225.     for (prevPtr = NULL, summaryPtr = nodePtr->summaryPtr;
  1226.         summaryPtr != NULL;
  1227.         prevPtr = summaryPtr, summaryPtr = summaryPtr->nextPtr) {
  1228.         if (summaryPtr->tagPtr != tagPtr) {
  1229.         continue;
  1230.         }
  1231.         summaryPtr->toggleCount += delta;
  1232.         if (summaryPtr->toggleCount > 0) {
  1233.         goto nextAncestor;
  1234.         }
  1235.         if (summaryPtr->toggleCount < 0) {
  1236.         panic("ChangeNodeToggleCount: negative toggle count");
  1237.         }
  1238.     
  1239.         /*
  1240.          * Zero count;  must remove this tag from the list.
  1241.          */
  1242.     
  1243.         if (prevPtr == NULL) {
  1244.         nodePtr->summaryPtr = summaryPtr->nextPtr;
  1245.         } else {
  1246.         prevPtr->nextPtr = summaryPtr->nextPtr;
  1247.         }
  1248.         ckfree((char *) summaryPtr);
  1249.         goto nextAncestor;
  1250.     }
  1251.     
  1252.     /*
  1253.      * This tag isn't in the list.  Add a new entry to the list.
  1254.      */
  1255.     
  1256.     if (delta < 0) {
  1257.         panic("ChangeNodeToggleCount: negative delta, no tag entry");
  1258.     }
  1259.     summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  1260.     summaryPtr->tagPtr = tagPtr;
  1261.     summaryPtr->toggleCount = delta;
  1262.     summaryPtr->nextPtr = nodePtr->summaryPtr;
  1263.     nodePtr->summaryPtr = summaryPtr;
  1264.  
  1265.     nextAncestor:
  1266.     continue;
  1267.     }
  1268. }
  1269.  
  1270. /*
  1271.  *----------------------------------------------------------------------
  1272.  *
  1273.  * TkBTreeStartSearch --
  1274.  *
  1275.  *    This procedure sets up a search for tag transitions involving
  1276.  *    a given tag (or all tags) in a given range of the text.
  1277.  *
  1278.  * Results:
  1279.  *    None.
  1280.  *
  1281.  * Side effects:
  1282.  *    The information at *searchPtr is set up so that subsequent calls
  1283.  *    to TkBTreeNextTag will return information about the locations of
  1284.  *    tag transitions.  Note that TkBTreeNextTag must be called to get
  1285.  *    the first transition.
  1286.  *
  1287.  *----------------------------------------------------------------------
  1288.  */
  1289.  
  1290. void
  1291. TkBTreeStartSearch(index1Ptr, index2Ptr, tagPtr, searchPtr)
  1292.     TkTextIndex *index1Ptr;        /* Search starts here.  Tag toggles
  1293.                      * at this position will not be
  1294.                      * returned. */
  1295.     TkTextIndex *index2Ptr;        /* Search stops here.  Tag toggles
  1296.                      * at this position *will* be
  1297.                      * returned. */
  1298.     TkTextTag *tagPtr;            /* Tag to search for.  NULL means
  1299.                      * search for any tag. */
  1300.     register TkTextSearch *searchPtr;    /* Where to store information about
  1301.                      * search's progress. */
  1302. {
  1303.     int offset;
  1304.  
  1305.     searchPtr->curIndex = *index1Ptr;
  1306.     searchPtr->segPtr = NULL;
  1307.     searchPtr->nextPtr = TkTextIndexToSeg(index1Ptr, &offset);
  1308.     searchPtr->curIndex.charIndex -= offset;
  1309.     searchPtr->lastPtr = TkTextIndexToSeg(index2Ptr, (int *) NULL);
  1310.     searchPtr->tagPtr = tagPtr;
  1311.     searchPtr->linesLeft = TkBTreeLineIndex(index2Ptr->linePtr) + 1
  1312.         - TkBTreeLineIndex(index1Ptr->linePtr);
  1313.     searchPtr->allTags = (tagPtr == NULL);
  1314.     if (searchPtr->linesLeft == 1) {
  1315.     /*
  1316.      * Starting and stopping segments are in the same line; mark the
  1317.      * search as over immediately if the second segment is before the
  1318.      * first.
  1319.      */
  1320.  
  1321.     if (index1Ptr->charIndex >= index2Ptr->charIndex) {
  1322.         searchPtr->linesLeft = 0;
  1323.     }
  1324.     }
  1325. }
  1326.  
  1327. /*
  1328.  *----------------------------------------------------------------------
  1329.  *
  1330.  * TkBTreeNextTag --
  1331.  *
  1332.  *    Once a tag search has begun, successive calls to this procedure
  1333.  *    return successive tag toggles.  Note:  it is NOT SAFE to call this
  1334.  *    procedure if characters have been inserted into or deleted from
  1335.  *    the B-tree since the call to TkBTreeStartSearch.
  1336.  *
  1337.  * Results:
  1338.  *    The return value is 1 if another toggle was found that met the
  1339.  *    criteria specified in the call to TkBTreeStartSearch;  in this
  1340.  *    case searchPtr->curIndex gives the toggle's position and
  1341.  *    searchPtr->curTagPtr points to its segment.  0 is returned if
  1342.  *    no more matching tag transitions were found; in this case
  1343.  *    searchPtr->curIndex is the same as searchPtr->stopIndex.
  1344.  *
  1345.  * Side effects:
  1346.  *    Information in *searchPtr is modified to update the state of the
  1347.  *    search and indicate where the next tag toggle is located.
  1348.  *
  1349.  *----------------------------------------------------------------------
  1350.  */
  1351.  
  1352. int
  1353. TkBTreeNextTag(searchPtr)
  1354.     register TkTextSearch *searchPtr;    /* Information about search in
  1355.                      * progress;  must have been set up by
  1356.                      * call to TkBTreeStartSearch. */
  1357. {
  1358.     register TkTextSegment *segPtr;
  1359.     register Node *nodePtr;
  1360.     register Summary *summaryPtr;
  1361.  
  1362.     if (searchPtr->linesLeft <= 0) {
  1363.     goto searchOver;
  1364.     }
  1365.  
  1366.     /*
  1367.      * The outermost loop iterates over lines that may potentially contain
  1368.      * a relevant tag transition, starting from the current segment in
  1369.      * the current line.
  1370.      */
  1371.  
  1372.     segPtr = searchPtr->nextPtr;
  1373.     while (1) {
  1374.     /*
  1375.      * Check for more tags on the current line.
  1376.      */
  1377.  
  1378.     for ( ; segPtr != NULL; segPtr = segPtr->nextPtr) {
  1379.         if (segPtr == searchPtr->lastPtr) {
  1380.         goto searchOver;
  1381.         }
  1382.         if (((segPtr->typePtr == &tkTextToggleOnType)
  1383.             || (segPtr->typePtr == &tkTextToggleOffType))
  1384.             && (searchPtr->allTags
  1385.             || (segPtr->body.toggle.tagPtr == searchPtr->tagPtr))) {
  1386.         searchPtr->segPtr = segPtr;
  1387.         searchPtr->nextPtr = segPtr->nextPtr;
  1388.         searchPtr->tagPtr = segPtr->body.toggle.tagPtr;
  1389.         return 1;
  1390.         }
  1391.         searchPtr->curIndex.charIndex += segPtr->size;
  1392.     }
  1393.     
  1394.     /*
  1395.      * See if there are more lines associated with the current parent
  1396.      * node.  If so, go back to the top of the loop to search the next
  1397.      * one.
  1398.      */
  1399.  
  1400.     nodePtr = searchPtr->curIndex.linePtr->parentPtr;
  1401.     searchPtr->curIndex.linePtr = searchPtr->curIndex.linePtr->nextPtr;
  1402.     searchPtr->linesLeft--;
  1403.     if (searchPtr->linesLeft <= 0) {
  1404.         goto searchOver;
  1405.     }
  1406.     if (searchPtr->curIndex.linePtr != NULL) {
  1407.         segPtr = searchPtr->curIndex.linePtr->segPtr;
  1408.         searchPtr->curIndex.charIndex = 0;
  1409.         continue;
  1410.     }
  1411.     
  1412.     /*
  1413.      * Search across and up through the B-tree's node hierarchy looking
  1414.      * for the next node that has a relevant tag transition somewhere in
  1415.      * its subtree.  Be sure to update linesLeft as we skip over large
  1416.      * chunks of lines.
  1417.      */
  1418.     
  1419.     while (1) {
  1420.         while (nodePtr->nextPtr == NULL) {
  1421.         if (nodePtr->parentPtr == NULL) {
  1422.             goto searchOver;
  1423.         }
  1424.         nodePtr = nodePtr->parentPtr;
  1425.         }
  1426.         nodePtr = nodePtr->nextPtr;
  1427.         for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1428.             summaryPtr = summaryPtr->nextPtr) {
  1429.         if ((searchPtr->allTags) ||
  1430.             (summaryPtr->tagPtr == searchPtr->tagPtr)) {
  1431.             goto gotNodeWithTag;
  1432.         }
  1433.         }
  1434.         searchPtr->linesLeft -= nodePtr->numLines;
  1435.     }
  1436.     
  1437.     /*
  1438.      * At this point we've found a subtree that has a relevant tag
  1439.      * transition.  Now search down (and across) through that subtree
  1440.      * to find the first level-0 node that has a relevant tag transition.
  1441.      */
  1442.     
  1443.     gotNodeWithTag:
  1444.     while (nodePtr->level > 0) {
  1445.         for (nodePtr = nodePtr->children.nodePtr; ;
  1446.             nodePtr = nodePtr->nextPtr) {
  1447.         for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1448.             summaryPtr = summaryPtr->nextPtr) {
  1449.             if ((searchPtr->allTags)
  1450.                 || (summaryPtr->tagPtr == searchPtr->tagPtr)) {
  1451.             goto nextChild;
  1452.             }
  1453.         }
  1454.         searchPtr->linesLeft -= nodePtr->numLines;
  1455.         if (nodePtr->nextPtr == NULL) {
  1456.             panic("TkBTreeNextTag found incorrect tag summary info.");
  1457.         }
  1458.         }
  1459.         nextChild:
  1460.         continue;
  1461.     }
  1462.     
  1463.     /*
  1464.      * Now we're down to a level-0 node that contains a line that contains
  1465.      * a relevant tag transition.  Set up line information and go back to
  1466.      * the beginning of the loop to search through lines.
  1467.      */
  1468.  
  1469.     searchPtr->curIndex.linePtr = nodePtr->children.linePtr;
  1470.     searchPtr->curIndex.charIndex = 0;
  1471.     segPtr = searchPtr->curIndex.linePtr->segPtr;
  1472.     if (searchPtr->linesLeft <= 0) {
  1473.         goto searchOver;
  1474.     }
  1475.     continue;
  1476.     }
  1477.  
  1478.     searchOver:
  1479.     searchPtr->linesLeft = 0;
  1480.     searchPtr->segPtr = NULL;
  1481.     return 0;
  1482. }
  1483.  
  1484. /*
  1485.  *----------------------------------------------------------------------
  1486.  *
  1487.  * TkBTreeCharTagged --
  1488.  *
  1489.  *    Determine whether a particular character has a particular tag.
  1490.  *
  1491.  * Results:
  1492.  *    The return value is 1 if the given tag is in effect at the
  1493.  *    character given by linePtr and ch, and 0 otherwise.
  1494.  *
  1495.  * Side effects:
  1496.  *    None.
  1497.  *
  1498.  *----------------------------------------------------------------------
  1499.  */
  1500.  
  1501. int
  1502. TkBTreeCharTagged(indexPtr, tagPtr)
  1503.     TkTextIndex *indexPtr;        /* Indicates a character position at
  1504.                      * which to check for a tag. */
  1505.     TkTextTag *tagPtr;            /* Tag of interest. */
  1506. {
  1507.     register Node *nodePtr;
  1508.     register TkTextLine *siblingLinePtr;
  1509.     register TkTextSegment *segPtr;
  1510.     TkTextSegment *toggleSegPtr;
  1511.     int toggles, index;
  1512.  
  1513.     /* 
  1514.      * Check for toggles for the tag in indexPtr's line but before
  1515.      * indexPtr.  If there is one, its type indicates whether or
  1516.      * not the character is tagged.
  1517.      */
  1518.  
  1519.     toggleSegPtr = NULL;
  1520.     for (index = 0, segPtr = indexPtr->linePtr->segPtr;
  1521.         (index + segPtr->size) <= indexPtr->charIndex;
  1522.         index += segPtr->size, segPtr = segPtr->nextPtr) {
  1523.     if (((segPtr->typePtr == &tkTextToggleOnType)
  1524.         || (segPtr->typePtr == &tkTextToggleOffType))
  1525.         && (segPtr->body.toggle.tagPtr == tagPtr)) {
  1526.         toggleSegPtr = segPtr;
  1527.     }
  1528.     }
  1529.     if (toggleSegPtr != NULL) {
  1530.     return (toggleSegPtr->typePtr == &tkTextToggleOnType);
  1531.     }
  1532.  
  1533.     /*
  1534.      * No toggle in this line.  Look for toggles for the tag in lines
  1535.      * that are predecessors of indexPtr->linePtr but under the same
  1536.      * level-0 node.
  1537.      */
  1538.  
  1539.     toggles = 0;
  1540.     for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
  1541.         siblingLinePtr != indexPtr->linePtr;
  1542.         siblingLinePtr = siblingLinePtr->nextPtr) {
  1543.     for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
  1544.         segPtr = segPtr->nextPtr) {
  1545.         if (((segPtr->typePtr == &tkTextToggleOnType)
  1546.             || (segPtr->typePtr == &tkTextToggleOffType))
  1547.             && (segPtr->body.toggle.tagPtr == tagPtr)) {
  1548.         toggleSegPtr = segPtr;
  1549.         }
  1550.     }
  1551.     }
  1552.     if (toggleSegPtr != NULL) {
  1553.     return (toggleSegPtr->typePtr == &tkTextToggleOnType);
  1554.     }
  1555.  
  1556.     /*
  1557.      * No toggle in this node.  Scan upwards through the ancestors of
  1558.      * this node, counting the number of toggles of the given tag in
  1559.      * siblings that precede that node.
  1560.      */
  1561.  
  1562.     toggles = 0;
  1563.     for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
  1564.         nodePtr = nodePtr->parentPtr) {
  1565.     register Node *siblingPtr;
  1566.     register Summary *summaryPtr;
  1567.  
  1568.     for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 
  1569.         siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
  1570.         for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
  1571.             summaryPtr = summaryPtr->nextPtr) {
  1572.         if (summaryPtr->tagPtr == tagPtr) {
  1573.             toggles += summaryPtr->toggleCount;
  1574.         }
  1575.         }
  1576.     }
  1577.     }
  1578.  
  1579.     /*
  1580.      * An odd number of toggles means that the tag is present at the
  1581.      * given point.
  1582.      */
  1583.  
  1584.     return toggles & 1;
  1585. }
  1586.  
  1587. /*
  1588.  *----------------------------------------------------------------------
  1589.  *
  1590.  * TkBTreeGetTags --
  1591.  *
  1592.  *    Return information about all of the tags that are associated
  1593.  *    with a particular character in a B-tree of text.
  1594.  *
  1595.  * Results:
  1596.  *    The return value is a malloc-ed array containing pointers to
  1597.  *    information for each of the tags that is associated with
  1598.  *    the character at the position given by linePtr and ch.  The
  1599.  *    word at *numTagsPtr is filled in with the number of pointers
  1600.  *    in the array.  It is up to the caller to free the array by
  1601.  *    passing it to free.  If there are no tags at the given character
  1602.  *    then a NULL pointer is returned and *numTagsPtr will be set to 0.
  1603.  *
  1604.  * Side effects:
  1605.  *    None.
  1606.  *
  1607.  *----------------------------------------------------------------------
  1608.  */
  1609.  
  1610.     /* ARGSUSED */
  1611. TkTextTag **
  1612. TkBTreeGetTags(indexPtr, numTagsPtr)
  1613.     TkTextIndex *indexPtr;    /* Indicates a particular position in
  1614.                  * the B-tree. */
  1615.     int *numTagsPtr;        /* Store number of tags found at this
  1616.                  * location. */
  1617. {
  1618.     register Node *nodePtr;
  1619.     register TkTextLine *siblingLinePtr;
  1620.     register TkTextSegment *segPtr;
  1621.     int src, dst, index;
  1622.     TagInfo tagInfo;
  1623. #define NUM_TAG_INFOS 10
  1624.  
  1625.     tagInfo.numTags = 0;
  1626.     tagInfo.arraySize = NUM_TAG_INFOS;
  1627.     tagInfo.tagPtrs = (TkTextTag **) ckalloc((unsigned)
  1628.         NUM_TAG_INFOS*sizeof(TkTextTag *));
  1629.     tagInfo.counts = (int *) ckalloc((unsigned)
  1630.         NUM_TAG_INFOS*sizeof(int));
  1631.  
  1632.     /*
  1633.      * Record tag toggles within the line of indexPtr but preceding
  1634.      * indexPtr.
  1635.      */
  1636.  
  1637.     for (index = 0, segPtr = indexPtr->linePtr->segPtr;
  1638.         (index + segPtr->size) <= indexPtr->charIndex;
  1639.         index += segPtr->size, segPtr = segPtr->nextPtr) {
  1640.     if ((segPtr->typePtr == &tkTextToggleOnType)
  1641.         || (segPtr->typePtr == &tkTextToggleOffType)) {
  1642.         IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
  1643.     }
  1644.     }
  1645.  
  1646.     /*
  1647.      * Record toggles for tags in lines that are predecessors of
  1648.      * indexPtr->linePtr but under the same level-0 node.
  1649.      */
  1650.  
  1651.     for (siblingLinePtr = indexPtr->linePtr->parentPtr->children.linePtr;
  1652.         siblingLinePtr != indexPtr->linePtr;
  1653.         siblingLinePtr = siblingLinePtr->nextPtr) {
  1654.     for (segPtr = siblingLinePtr->segPtr; segPtr != NULL;
  1655.         segPtr = segPtr->nextPtr) {
  1656.         if ((segPtr->typePtr == &tkTextToggleOnType)
  1657.             || (segPtr->typePtr == &tkTextToggleOffType)) {
  1658.         IncCount(segPtr->body.toggle.tagPtr, 1, &tagInfo);
  1659.         }
  1660.     }
  1661.     }
  1662.  
  1663.     /*
  1664.      * For each node in the ancestry of this line, record tag toggles
  1665.      * for all siblings that precede that node.
  1666.      */
  1667.  
  1668.     for (nodePtr = indexPtr->linePtr->parentPtr; nodePtr->parentPtr != NULL;
  1669.         nodePtr = nodePtr->parentPtr) {
  1670.     register Node *siblingPtr;
  1671.     register Summary *summaryPtr;
  1672.  
  1673.     for (siblingPtr = nodePtr->parentPtr->children.nodePtr; 
  1674.         siblingPtr != nodePtr; siblingPtr = siblingPtr->nextPtr) {
  1675.         for (summaryPtr = siblingPtr->summaryPtr; summaryPtr != NULL;
  1676.             summaryPtr = summaryPtr->nextPtr) {
  1677.         if (summaryPtr->toggleCount & 1) {
  1678.             IncCount(summaryPtr->tagPtr, summaryPtr->toggleCount,
  1679.                 &tagInfo);
  1680.         }
  1681.         }
  1682.     }
  1683.     }
  1684.  
  1685.     /*
  1686.      * Go through the tag information and squash out all of the tags
  1687.      * that have even toggle counts (these tags exist before the point
  1688.      * of interest, but not at the desired character itself).
  1689.      */
  1690.  
  1691.     for (src = 0, dst = 0; src < tagInfo.numTags; src++) {
  1692.     if (tagInfo.counts[src] & 1) {
  1693.         tagInfo.tagPtrs[dst] = tagInfo.tagPtrs[src];
  1694.         dst++;
  1695.     }
  1696.     }
  1697.     *numTagsPtr = dst;
  1698.     ckfree((char *) tagInfo.counts);
  1699.     if (dst == 0) {
  1700.     ckfree((char *) tagInfo.tagPtrs);
  1701.     return NULL;
  1702.     }
  1703.     return tagInfo.tagPtrs;
  1704. }
  1705.  
  1706. /*
  1707.  *----------------------------------------------------------------------
  1708.  *
  1709.  * IncCount --
  1710.  *
  1711.  *    This is a utility procedure used by TkBTreeGetTags.  It
  1712.  *    increments the count for a particular tag, adding a new
  1713.  *    entry for that tag if there wasn't one previously.
  1714.  *
  1715.  * Results:
  1716.  *    None.
  1717.  *
  1718.  * Side effects:
  1719.  *    The information at *tagInfoPtr may be modified, and the arrays
  1720.  *    may be reallocated to make them larger.
  1721.  *
  1722.  *----------------------------------------------------------------------
  1723.  */
  1724.  
  1725. static void
  1726. IncCount(tagPtr, inc, tagInfoPtr)
  1727.     TkTextTag *tagPtr;        /* Handle for tag. */
  1728.     int inc;            /* Amount by which to increment tag count. */
  1729.     TagInfo *tagInfoPtr;    /* Holds cumulative information about tags;
  1730.                  * increment count here. */
  1731. {
  1732.     register TkTextTag **tagPtrPtr;
  1733.     int count;
  1734.  
  1735.     for (tagPtrPtr = tagInfoPtr->tagPtrs, count = tagInfoPtr->numTags;
  1736.         count > 0; tagPtrPtr++, count--) {
  1737.     if (*tagPtrPtr == tagPtr) {
  1738.         tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
  1739.         return;
  1740.     }
  1741.     }
  1742.  
  1743.     /*
  1744.      * There isn't currently an entry for this tag, so we have to
  1745.      * make a new one.  If the arrays are full, then enlarge the
  1746.      * arrays first.
  1747.      */
  1748.  
  1749.     if (tagInfoPtr->numTags == tagInfoPtr->arraySize) {
  1750.     TkTextTag **newTags;
  1751.     int *newCounts, newSize;
  1752.  
  1753.     newSize = 2*tagInfoPtr->arraySize;
  1754.     newTags = (TkTextTag **) ckalloc((unsigned)
  1755.         (newSize*sizeof(TkTextTag *)));
  1756.     memcpy((VOID *) newTags, (VOID *) tagInfoPtr->tagPtrs,
  1757.         tagInfoPtr->arraySize * sizeof(TkTextTag *));
  1758.     ckfree((char *) tagInfoPtr->tagPtrs);
  1759.     tagInfoPtr->tagPtrs = newTags;
  1760.     newCounts = (int *) ckalloc((unsigned) (newSize*sizeof(int)));
  1761.     memcpy((VOID *) newCounts, (VOID *) tagInfoPtr->counts,
  1762.         tagInfoPtr->arraySize * sizeof(int));
  1763.     ckfree((char *) tagInfoPtr->counts);
  1764.     tagInfoPtr->counts = newCounts;
  1765.     tagInfoPtr->arraySize = newSize;
  1766.     }
  1767.  
  1768.     tagInfoPtr->tagPtrs[tagInfoPtr->numTags] = tagPtr;
  1769.     tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
  1770.     tagInfoPtr->numTags++;
  1771. }
  1772.  
  1773. /*
  1774.  *----------------------------------------------------------------------
  1775.  *
  1776.  * TkBTreeCheck --
  1777.  *
  1778.  *    This procedure runs a set of consistency checks over a B-tree
  1779.  *    and panics if any inconsistencies are found.
  1780.  *
  1781.  * Results:
  1782.  *    None.
  1783.  *
  1784.  * Side effects:
  1785.  *    If a structural defect is found, the procedure panics with an
  1786.  *    error message.
  1787.  *
  1788.  *----------------------------------------------------------------------
  1789.  */
  1790.  
  1791. void
  1792. TkBTreeCheck(tree)
  1793.     TkTextBTree tree;        /* Tree to check. */
  1794. {
  1795.     BTree *treePtr = (BTree *) tree;
  1796.     register Summary *summaryPtr;
  1797.     register Node *nodePtr;
  1798.     register TkTextLine *linePtr;
  1799.     register TkTextSegment *segPtr;
  1800.  
  1801.     /*
  1802.      * Make sure that overall there is an even count of tag transitions
  1803.      * for the whole tree.
  1804.      */
  1805.  
  1806.     for (summaryPtr = treePtr->rootPtr->summaryPtr; summaryPtr != NULL;
  1807.         summaryPtr = summaryPtr->nextPtr) {
  1808.     if (summaryPtr->toggleCount & 1) {
  1809.         panic("TkBTreeCheck found odd toggle count for \"%s\" (%d)",
  1810.             summaryPtr->tagPtr->name, summaryPtr->toggleCount);
  1811.     }
  1812.     }
  1813.  
  1814.     /*
  1815.      * Call a recursive procedure to do the main body of checks.
  1816.      */
  1817.  
  1818.     nodePtr = treePtr->rootPtr;
  1819.     CheckNodeConsistency(treePtr->rootPtr);
  1820.  
  1821.     /*
  1822.      * Make sure that there are at least two lines in the text and
  1823.      * that the last line has no characters except a newline.
  1824.      */
  1825.  
  1826.     if (nodePtr->numLines < 2) {
  1827.     panic("TkBTreeCheck: less than 2 lines in tree");
  1828.     }
  1829.     while (nodePtr->level > 0) {
  1830.     nodePtr = nodePtr->children.nodePtr;
  1831.     while (nodePtr->nextPtr != NULL) {
  1832.         nodePtr = nodePtr->nextPtr;
  1833.     }
  1834.     }
  1835.     linePtr = nodePtr->children.linePtr;
  1836.     while (linePtr->nextPtr != NULL) {
  1837.     linePtr = linePtr->nextPtr;
  1838.     }
  1839.     segPtr = linePtr->segPtr;
  1840.     while ((segPtr->typePtr == &tkTextToggleOffType)
  1841.         || (segPtr->typePtr == &tkTextRightMarkType)
  1842.         || (segPtr->typePtr == &tkTextLeftMarkType)) {
  1843.     /*
  1844.      * It's OK to toggle a tag off in the last line, but
  1845.      * not to start a new range.  It's also OK to have marks
  1846.      * in the last line.
  1847.      */
  1848.  
  1849.     segPtr = segPtr->nextPtr;
  1850.     }
  1851.     if (segPtr->typePtr != &tkTextCharType) {
  1852.     panic("TkBTreeCheck: last line has bogus segment type");
  1853.     }
  1854.     if (segPtr->nextPtr != NULL) {
  1855.     panic("TkBTreeCheck: last line has too many segments");
  1856.     }
  1857.     if (segPtr->size != 1) {
  1858.     panic("TkBTreeCheck: last line has wrong # characters: %d",
  1859.         segPtr->size);
  1860.     }
  1861.     if ((segPtr->body.chars[0] != '\n') || (segPtr->body.chars[1] != 0)) {
  1862.     panic("TkBTreeCheck: last line had bad value: %s",
  1863.         segPtr->body.chars);
  1864.     }
  1865. }
  1866.  
  1867. /*
  1868.  *----------------------------------------------------------------------
  1869.  *
  1870.  * CheckNodeConsistency --
  1871.  *
  1872.  *    This procedure is called as part of consistency checking for
  1873.  *    B-trees:  it checks several aspects of a node and also runs
  1874.  *    checks recursively on the node's children.
  1875.  *
  1876.  * Results:
  1877.  *    None.
  1878.  *
  1879.  * Side effects:
  1880.  *    If anything suspicious is found in the tree structure, the
  1881.  *    procedure panics.
  1882.  *
  1883.  *----------------------------------------------------------------------
  1884.  */
  1885.  
  1886. static void
  1887. CheckNodeConsistency(nodePtr)
  1888.     register Node *nodePtr;        /* Node whose subtree should be
  1889.                      * checked. */
  1890. {
  1891.     register Node *childNodePtr;
  1892.     register Summary *summaryPtr, *summaryPtr2;
  1893.     register TkTextLine *linePtr;
  1894.     register TkTextSegment *segPtr;
  1895.     int numChildren, numLines, toggleCount, minChildren;
  1896.  
  1897.     if (nodePtr->parentPtr != NULL) {
  1898.     minChildren = MIN_CHILDREN;
  1899.     } else if (nodePtr->level > 0) {
  1900.     minChildren = 2;
  1901.     } else  {
  1902.     minChildren = 1;
  1903.     }
  1904.     if ((nodePtr->numChildren < minChildren)
  1905.         || (nodePtr->numChildren > MAX_CHILDREN)) {
  1906.     panic("CheckNodeConsistency: bad child count (%d)",
  1907.         nodePtr->numChildren);
  1908.     }
  1909.  
  1910.     numChildren = 0;
  1911.     numLines = 0;
  1912.     if (nodePtr->level == 0) {
  1913.     for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  1914.         linePtr = linePtr->nextPtr) {
  1915.         if (linePtr->parentPtr != nodePtr) {
  1916.         panic("CheckNodeConsistency: line doesn't point to parent");
  1917.         }
  1918.         if (linePtr->segPtr == NULL) {
  1919.         panic("CheckNodeConsistency: line has no segments");
  1920.         }
  1921.         for (segPtr = linePtr->segPtr; segPtr != NULL;
  1922.             segPtr = segPtr->nextPtr) {
  1923.         if (segPtr->typePtr->checkProc != NULL) {
  1924.             (*segPtr->typePtr->checkProc)(segPtr, linePtr);
  1925.         }
  1926.         if ((segPtr->size == 0) && (!segPtr->typePtr->leftGravity)
  1927.             && (segPtr->nextPtr != NULL)
  1928.             && (segPtr->nextPtr->size == 0)
  1929.             && (segPtr->nextPtr->typePtr->leftGravity)) {
  1930.             panic("CheckNodeConsistency: wrong segment order for gravity");
  1931.         }
  1932.         if ((segPtr->nextPtr == NULL)
  1933.             && (segPtr->typePtr != &tkTextCharType)) {
  1934.             panic("CheckNodeConsistency: line ended with wrong type");
  1935.         }
  1936.         }
  1937.         numChildren++;
  1938.         numLines++;
  1939.     }
  1940.     } else {
  1941.     for (childNodePtr = nodePtr->children.nodePtr; childNodePtr != NULL;
  1942.         childNodePtr = childNodePtr->nextPtr) {
  1943.         if (childNodePtr->parentPtr != nodePtr) {
  1944.         panic("CheckNodeConsistency: node doesn't point to parent");
  1945.         }
  1946.         if (childNodePtr->level != (nodePtr->level-1)) {
  1947.         panic("CheckNodeConsistency: level mismatch (%d %d)",
  1948.             nodePtr->level, childNodePtr->level);
  1949.         }
  1950.         CheckNodeConsistency(childNodePtr);
  1951.         for (summaryPtr = childNodePtr->summaryPtr; summaryPtr != NULL;
  1952.             summaryPtr = summaryPtr->nextPtr) {
  1953.         for (summaryPtr2 = nodePtr->summaryPtr; ;
  1954.             summaryPtr2 = summaryPtr2->nextPtr) {
  1955.             if (summaryPtr2 == NULL) {
  1956.             panic("CheckNodeConsistency: node tag \"%s\" not %s",
  1957.                 summaryPtr->tagPtr->name,
  1958.                 "present in parent summaries");
  1959.             }
  1960.             if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
  1961.             break;
  1962.             }
  1963.         }
  1964.         }
  1965.         numChildren++;
  1966.         numLines += childNodePtr->numLines;
  1967.     }
  1968.     }
  1969.     if (numChildren != nodePtr->numChildren) {
  1970.     panic("CheckNodeConsistency: mismatch in numChildren (%d %d)",
  1971.         numChildren, nodePtr->numChildren);
  1972.     }
  1973.     if (numLines != nodePtr->numLines) {
  1974.     panic("CheckNodeConsistency: mismatch in numLines (%d %d)",
  1975.         numLines, nodePtr->numLines);
  1976.     }
  1977.  
  1978.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  1979.         summaryPtr = summaryPtr->nextPtr) {
  1980.     toggleCount = 0;
  1981.     if (nodePtr->level == 0) {
  1982.         for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  1983.             linePtr = linePtr->nextPtr) {
  1984.         for (segPtr = linePtr->segPtr; segPtr != NULL;
  1985.             segPtr = segPtr->nextPtr) {
  1986.             if ((segPtr->typePtr != &tkTextToggleOnType)
  1987.                 && (segPtr->typePtr != &tkTextToggleOffType)) {
  1988.             continue;
  1989.             }
  1990.             if (segPtr->body.toggle.tagPtr == summaryPtr->tagPtr) {
  1991.             toggleCount ++;
  1992.             }
  1993.         }
  1994.         }
  1995.     } else {
  1996.         for (childNodePtr = nodePtr->children.nodePtr;
  1997.             childNodePtr != NULL;
  1998.             childNodePtr = childNodePtr->nextPtr) {
  1999.         for (summaryPtr2 = childNodePtr->summaryPtr;
  2000.             summaryPtr2 != NULL;
  2001.             summaryPtr2 = summaryPtr2->nextPtr) {
  2002.             if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
  2003.             toggleCount += summaryPtr2->toggleCount;
  2004.             }
  2005.         }
  2006.         }
  2007.     }
  2008.     if (toggleCount != summaryPtr->toggleCount) {
  2009.         panic("CheckNodeConsistency: mismatch in toggleCount (%d %d)",
  2010.             toggleCount, summaryPtr->toggleCount);
  2011.     }
  2012.     for (summaryPtr2 = summaryPtr->nextPtr; summaryPtr2 != NULL;
  2013.         summaryPtr2 = summaryPtr2->nextPtr) {
  2014.         if (summaryPtr2->tagPtr == summaryPtr->tagPtr) {
  2015.         panic("CheckNodeConsistency: duplicated node tag: %s",
  2016.             summaryPtr->tagPtr->name);
  2017.         }
  2018.     }
  2019.     }
  2020. }
  2021.  
  2022. /*
  2023.  *----------------------------------------------------------------------
  2024.  *
  2025.  * Rebalance --
  2026.  *
  2027.  *    This procedure is called when a node of a B-tree appears to be
  2028.  *    out of balance (too many children, or too few).  It rebalances
  2029.  *    that node and all of its ancestors in the tree.
  2030.  *
  2031.  * Results:
  2032.  *    None.
  2033.  *
  2034.  * Side effects:
  2035.  *    The internal structure of treePtr may change.
  2036.  *
  2037.  *----------------------------------------------------------------------
  2038.  */
  2039.  
  2040. static void
  2041. Rebalance(treePtr, nodePtr)
  2042.     BTree *treePtr;            /* Tree that is being rebalanced. */
  2043.     register Node *nodePtr;        /* Node that may be out of balance. */
  2044. {
  2045.     /*
  2046.      * Loop over the entire ancestral chain of the node, working up
  2047.      * through the tree one node at a time until the root node has
  2048.      * been processed.
  2049.      */
  2050.  
  2051.     for ( ; nodePtr != NULL; nodePtr = nodePtr->parentPtr) {
  2052.     register Node *newPtr, *childPtr;
  2053.     register TkTextLine *linePtr;
  2054.     int i;
  2055.  
  2056.     /*
  2057.      * Check to see if the node has too many children.  If it does,
  2058.      * then split off all but the first MIN_CHILDREN into a separate
  2059.      * node following the original one.  Then repeat until the
  2060.      * node has a decent size.
  2061.      */
  2062.  
  2063.     if (nodePtr->numChildren > MAX_CHILDREN) {
  2064.         while (1) {
  2065.         /*
  2066.          * If the node being split is the root node, then make a
  2067.          * new root node above it first.
  2068.          */
  2069.     
  2070.         if (nodePtr->parentPtr == NULL) {
  2071.             newPtr = (Node *) ckalloc(sizeof(Node));
  2072.             newPtr->parentPtr = NULL;
  2073.             newPtr->nextPtr = NULL;
  2074.             newPtr->summaryPtr = NULL;
  2075.             newPtr->level = nodePtr->level + 1;
  2076.             newPtr->children.nodePtr = nodePtr;
  2077.             newPtr->numChildren = 1;
  2078.             newPtr->numLines = nodePtr->numLines;
  2079.             RecomputeNodeCounts(newPtr);
  2080.             treePtr->rootPtr = newPtr;
  2081.         }
  2082.         newPtr = (Node *) ckalloc(sizeof(Node));
  2083.         newPtr->parentPtr = nodePtr->parentPtr;
  2084.         newPtr->nextPtr = nodePtr->nextPtr;
  2085.         nodePtr->nextPtr = newPtr;
  2086.         newPtr->summaryPtr = NULL;
  2087.         newPtr->level = nodePtr->level;
  2088.         newPtr->numChildren = nodePtr->numChildren - MIN_CHILDREN;
  2089.         if (nodePtr->level == 0) {
  2090.             for (i = MIN_CHILDREN-1,
  2091.                 linePtr = nodePtr->children.linePtr;
  2092.                 i > 0; i--, linePtr = linePtr->nextPtr) {
  2093.             /* Empty loop body. */
  2094.             }
  2095.             newPtr->children.linePtr = linePtr->nextPtr;
  2096.             linePtr->nextPtr = NULL;
  2097.         } else {
  2098.             for (i = MIN_CHILDREN-1,
  2099.                 childPtr = nodePtr->children.nodePtr;
  2100.                 i > 0; i--, childPtr = childPtr->nextPtr) {
  2101.             /* Empty loop body. */
  2102.             }
  2103.             newPtr->children.nodePtr = childPtr->nextPtr;
  2104.             childPtr->nextPtr = NULL;
  2105.         }
  2106.         RecomputeNodeCounts(nodePtr);
  2107.         nodePtr->parentPtr->numChildren++;
  2108.         nodePtr = newPtr;
  2109.         if (nodePtr->numChildren <= MAX_CHILDREN) {
  2110.             RecomputeNodeCounts(nodePtr);
  2111.             break;
  2112.         }
  2113.         }
  2114.     }
  2115.  
  2116.     while (nodePtr->numChildren < MIN_CHILDREN) {
  2117.         register Node *otherPtr;
  2118.         Node *halfwayNodePtr = NULL;    /* Initialization needed only */
  2119.         TkTextLine *halfwayLinePtr = NULL;    /* to prevent cc warnings. */
  2120.         int totalChildren, firstChildren, i;
  2121.  
  2122.         /*
  2123.          * Too few children for this node.  If this is the root then,
  2124.          * it's OK for it to have less than MIN_CHILDREN children
  2125.          * as long as it's got at least two.  If it has only one
  2126.          * (and isn't at level 0), then chop the root node out of
  2127.          * the tree and use its child as the new root.
  2128.          */
  2129.  
  2130.         if (nodePtr->parentPtr == NULL) {
  2131.         if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
  2132.             treePtr->rootPtr = nodePtr->children.nodePtr;
  2133.             treePtr->rootPtr->parentPtr = NULL;
  2134.             DeleteSummaries(nodePtr->summaryPtr);
  2135.             ckfree((char *) nodePtr);
  2136.         }
  2137.         return;
  2138.         }
  2139.  
  2140.         /*
  2141.          * Not the root.  Make sure that there are siblings to
  2142.          * balance with.
  2143.          */
  2144.  
  2145.         if (nodePtr->parentPtr->numChildren < 2) {
  2146.         Rebalance(treePtr, nodePtr->parentPtr);
  2147.         continue;
  2148.         }
  2149.  
  2150.         /*
  2151.          * Find a sibling neighbor to borrow from, and arrange for
  2152.          * nodePtr to be the earlier of the pair.
  2153.          */
  2154.  
  2155.         if (nodePtr->nextPtr == NULL) {
  2156.         for (otherPtr = nodePtr->parentPtr->children.nodePtr;
  2157.             otherPtr->nextPtr != nodePtr;
  2158.             otherPtr = otherPtr->nextPtr) {
  2159.             /* Empty loop body. */
  2160.         }
  2161.         nodePtr = otherPtr;
  2162.         }
  2163.         otherPtr = nodePtr->nextPtr;
  2164.  
  2165.         /*
  2166.          * We're going to either merge the two siblings together
  2167.          * into one node or redivide the children among them to
  2168.          * balance their loads.  As preparation, join their two
  2169.          * child lists into a single list and remember the half-way
  2170.          * point in the list.
  2171.          */
  2172.  
  2173.         totalChildren = nodePtr->numChildren + otherPtr->numChildren;
  2174.         firstChildren = totalChildren/2;
  2175.         if (nodePtr->children.nodePtr == NULL) {
  2176.         nodePtr->children = otherPtr->children;
  2177.         otherPtr->children.nodePtr = NULL;
  2178.         otherPtr->children.linePtr = NULL;
  2179.         }
  2180.         if (nodePtr->level == 0) {
  2181.         register TkTextLine *linePtr;
  2182.  
  2183.         for (linePtr = nodePtr->children.linePtr, i = 1;
  2184.             linePtr->nextPtr != NULL;
  2185.             linePtr = linePtr->nextPtr, i++) {
  2186.             if (i == firstChildren) {
  2187.             halfwayLinePtr = linePtr;
  2188.             }
  2189.         }
  2190.         linePtr->nextPtr = otherPtr->children.linePtr;
  2191.         while (i <= firstChildren) {
  2192.             halfwayLinePtr = linePtr;
  2193.             linePtr = linePtr->nextPtr;
  2194.             i++;
  2195.         }
  2196.         } else {
  2197.         register Node *childPtr;
  2198.  
  2199.         for (childPtr = nodePtr->children.nodePtr, i = 1;
  2200.             childPtr->nextPtr != NULL;
  2201.             childPtr = childPtr->nextPtr, i++) {
  2202.             if (i <= firstChildren) {
  2203.             if (i == firstChildren) {
  2204.                 halfwayNodePtr = childPtr;
  2205.             }
  2206.             }
  2207.         }
  2208.         childPtr->nextPtr = otherPtr->children.nodePtr;
  2209.         while (i <= firstChildren) {
  2210.             halfwayNodePtr = childPtr;
  2211.             childPtr = childPtr->nextPtr;
  2212.             i++;
  2213.         }
  2214.         }
  2215.  
  2216.         /*
  2217.          * If the two siblings can simply be merged together, do it.
  2218.          */
  2219.  
  2220.         if (totalChildren <= MAX_CHILDREN) {
  2221.         RecomputeNodeCounts(nodePtr);
  2222.         nodePtr->nextPtr = otherPtr->nextPtr;
  2223.         nodePtr->parentPtr->numChildren--;
  2224.         DeleteSummaries(otherPtr->summaryPtr);
  2225.         ckfree((char *) otherPtr);
  2226.         continue;
  2227.         }
  2228.  
  2229.         /*
  2230.          * The siblings can't be merged, so just divide their
  2231.          * children evenly between them.
  2232.          */
  2233.  
  2234.         if (nodePtr->level == 0) {
  2235.         otherPtr->children.linePtr = halfwayLinePtr->nextPtr;
  2236.         halfwayLinePtr->nextPtr = NULL;
  2237.         } else {
  2238.         otherPtr->children.nodePtr = halfwayNodePtr->nextPtr;
  2239.         halfwayNodePtr->nextPtr = NULL;
  2240.         }
  2241.         RecomputeNodeCounts(nodePtr);
  2242.         RecomputeNodeCounts(otherPtr);
  2243.     }
  2244.     }
  2245. }
  2246.  
  2247. /*
  2248.  *----------------------------------------------------------------------
  2249.  *
  2250.  * RecomputeNodeCounts --
  2251.  *
  2252.  *    This procedure is called to recompute all the counts in a node
  2253.  *    (tags, child information, etc.) by scanning the information in
  2254.  *    its descendants.  This procedure is called during rebalancing
  2255.  *    when a node's child structure has changed.
  2256.  *
  2257.  * Results:
  2258.  *    None.
  2259.  *
  2260.  * Side effects:
  2261.  *    The tag counts for nodePtr are modified to reflect its current
  2262.  *    child structure, as are its numChildren and numLines fields.
  2263.  *    Also, all of the childrens' parentPtr fields are made to point
  2264.  *    to nodePtr.
  2265.  *
  2266.  *----------------------------------------------------------------------
  2267.  */
  2268.  
  2269. static void
  2270. RecomputeNodeCounts(nodePtr)
  2271.     register Node *nodePtr;        /* Node whose tag summary information
  2272.                      * must be recomputed. */
  2273. {
  2274.     register Summary *summaryPtr, *summaryPtr2;
  2275.     register Node *childPtr;
  2276.     register TkTextLine *linePtr;
  2277.     register TkTextSegment *segPtr;
  2278.     TkTextTag *tagPtr;
  2279.  
  2280.     /*
  2281.      * Zero out all the existing counts for the node, but don't delete
  2282.      * the existing Summary records (most of them will probably be reused).
  2283.      */
  2284.  
  2285.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL;
  2286.         summaryPtr = summaryPtr->nextPtr) {
  2287.     summaryPtr->toggleCount = 0;
  2288.     }
  2289.     nodePtr->numChildren = 0;
  2290.     nodePtr->numLines = 0;
  2291.  
  2292.     /*
  2293.      * Scan through the children, adding the childrens' tag counts into
  2294.      * the node's tag counts and adding new Summary structures if
  2295.      * necessary.
  2296.      */
  2297.  
  2298.     if (nodePtr->level == 0) {
  2299.     for (linePtr = nodePtr->children.linePtr; linePtr != NULL;
  2300.         linePtr = linePtr->nextPtr) {
  2301.         nodePtr->numChildren++;
  2302.         nodePtr->numLines++;
  2303.         linePtr->parentPtr = nodePtr;
  2304.         for (segPtr = linePtr->segPtr; segPtr != NULL;
  2305.             segPtr = segPtr->nextPtr) {
  2306.         if (((segPtr->typePtr != &tkTextToggleOnType)
  2307.             && (segPtr->typePtr != &tkTextToggleOffType))
  2308.             || !(segPtr->body.toggle.inNodeCounts)) {
  2309.             continue;
  2310.         }
  2311.         tagPtr = segPtr->body.toggle.tagPtr;
  2312.         for (summaryPtr = nodePtr->summaryPtr; ;
  2313.             summaryPtr = summaryPtr->nextPtr) {
  2314.             if (summaryPtr == NULL) {
  2315.             summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  2316.             summaryPtr->tagPtr = tagPtr;
  2317.             summaryPtr->toggleCount = 1;
  2318.             summaryPtr->nextPtr = nodePtr->summaryPtr;
  2319.             nodePtr->summaryPtr = summaryPtr;
  2320.             break;
  2321.             }
  2322.             if (summaryPtr->tagPtr == tagPtr) {
  2323.             summaryPtr->toggleCount++;
  2324.             break;
  2325.             }
  2326.         }
  2327.         }
  2328.     }
  2329.     } else {
  2330.     for (childPtr = nodePtr->children.nodePtr; childPtr != NULL;
  2331.         childPtr = childPtr->nextPtr) {
  2332.         nodePtr->numChildren++;
  2333.         nodePtr->numLines += childPtr->numLines;
  2334.         childPtr->parentPtr = nodePtr;
  2335.         for (summaryPtr2 = childPtr->summaryPtr; summaryPtr2 != NULL;
  2336.             summaryPtr2 = summaryPtr2->nextPtr) {
  2337.         for (summaryPtr = nodePtr->summaryPtr; ;
  2338.             summaryPtr = summaryPtr->nextPtr) {
  2339.             if (summaryPtr == NULL) {
  2340.             summaryPtr = (Summary *) ckalloc(sizeof(Summary));
  2341.             summaryPtr->tagPtr = summaryPtr2->tagPtr;
  2342.             summaryPtr->toggleCount = summaryPtr2->toggleCount;
  2343.             summaryPtr->nextPtr = nodePtr->summaryPtr;
  2344.             nodePtr->summaryPtr = summaryPtr;
  2345.             break;
  2346.             }
  2347.             if (summaryPtr->tagPtr == summaryPtr2->tagPtr) {
  2348.             summaryPtr->toggleCount += summaryPtr2->toggleCount;
  2349.             break;
  2350.             }
  2351.         }
  2352.         }
  2353.     }
  2354.     }
  2355.  
  2356.     /*
  2357.      * Scan through the node's tag records again and delete any Summary
  2358.      * records that still have a zero count.
  2359.      */
  2360.  
  2361.     summaryPtr2 = NULL;
  2362.     for (summaryPtr = nodePtr->summaryPtr; summaryPtr != NULL; ) {
  2363.     if (summaryPtr->toggleCount > 0) {
  2364.         summaryPtr2 = summaryPtr;
  2365.         summaryPtr = summaryPtr->nextPtr;
  2366.         continue;
  2367.     }
  2368.     if (summaryPtr2 != NULL) {
  2369.         summaryPtr2->nextPtr = summaryPtr->nextPtr;
  2370.         ckfree((char *) summaryPtr);
  2371.         summaryPtr = summaryPtr2->nextPtr;
  2372.     } else {
  2373.         nodePtr->summaryPtr = summaryPtr->nextPtr;
  2374.         ckfree((char *) summaryPtr);
  2375.         summaryPtr = nodePtr->summaryPtr;
  2376.     }
  2377.     }
  2378. }
  2379.  
  2380. /*
  2381.  *----------------------------------------------------------------------
  2382.  *
  2383.  * TkBTreeNumLines --
  2384.  *
  2385.  *    This procedure returns a count of the number of lines of
  2386.  *    text present in a given B-tree.
  2387.  *
  2388.  * Results:
  2389.  *    The return value is a count of the number of usable lines
  2390.  *    in tree (i.e. it doesn't include the dummy line that is just
  2391.  *     used to mark the end of the tree).
  2392.  *
  2393.  * Side effects:
  2394.  *    None.
  2395.  *
  2396.  *----------------------------------------------------------------------
  2397.  */
  2398.  
  2399. int
  2400. TkBTreeNumLines(tree)
  2401.     TkTextBTree tree;            /* Information about tree. */
  2402. {
  2403.     BTree *treePtr = (BTree *) tree;
  2404.     return treePtr->rootPtr->numLines - 1;
  2405. }
  2406.  
  2407. /*
  2408.  *--------------------------------------------------------------
  2409.  *
  2410.  * CharSplitProc --
  2411.  *
  2412.  *    This procedure implements splitting for character segments.
  2413.  *
  2414.  * Results:
  2415.  *    The return value is a pointer to a chain of two segments
  2416.  *    that have the same characters as segPtr except split
  2417.  *    among the two segments.
  2418.  *
  2419.  * Side effects:
  2420.  *    Storage for segPtr is freed.
  2421.  *
  2422.  *--------------------------------------------------------------
  2423.  */
  2424.  
  2425. static TkTextSegment *
  2426. CharSplitProc(segPtr, index)
  2427.     TkTextSegment *segPtr;        /* Pointer to segment to split. */
  2428.     int index;                /* Position within segment at which
  2429.                      * to split. */
  2430. {
  2431.     TkTextSegment *newPtr1, *newPtr2;
  2432.  
  2433.     newPtr1 = (TkTextSegment *) ckalloc(CSEG_SIZE(index));
  2434.     newPtr2 = (TkTextSegment *) ckalloc(
  2435.         CSEG_SIZE(segPtr->size - index));
  2436.     newPtr1->typePtr = &tkTextCharType;
  2437.     newPtr1->nextPtr = newPtr2;
  2438.     newPtr1->size = index;
  2439.     strncpy(newPtr1->body.chars, segPtr->body.chars, (size_t) index);
  2440.     newPtr1->body.chars[index] = 0;
  2441.     newPtr2->typePtr = &tkTextCharType;
  2442.     newPtr2->nextPtr = segPtr->nextPtr;
  2443.     newPtr2->size = segPtr->size - index;
  2444.     strcpy(newPtr2->body.chars, segPtr->body.chars + index);
  2445.     ckfree((char*) segPtr);
  2446.     return newPtr1;
  2447. }
  2448.  
  2449. /*
  2450.  *--------------------------------------------------------------
  2451.  *
  2452.  * CharCleanupProc --
  2453.  *
  2454.  *    This procedure merges adjacent character segments into
  2455.  *    a single character segment, if possible.
  2456.  *
  2457.  * Results:
  2458.  *    The return value is a pointer to the first segment in
  2459.  *    the (new) list of segments that used to start with segPtr.
  2460.  *
  2461.  * Side effects:
  2462.  *    Storage for the segments may be allocated and freed.
  2463.  *
  2464.  *--------------------------------------------------------------
  2465.  */
  2466.  
  2467.     /* ARGSUSED */
  2468. static TkTextSegment *
  2469. CharCleanupProc(segPtr, linePtr)
  2470.     TkTextSegment *segPtr;        /* Pointer to first of two adjacent
  2471.                      * segments to join. */
  2472.     TkTextLine *linePtr;        /* Line containing segments (not
  2473.                      * used). */
  2474. {
  2475.     TkTextSegment *segPtr2, *newPtr;
  2476.  
  2477.     segPtr2 = segPtr->nextPtr;
  2478.     if ((segPtr2 == NULL) || (segPtr2->typePtr != &tkTextCharType)) {
  2479.     return segPtr;
  2480.     }
  2481.     newPtr = (TkTextSegment *) ckalloc(CSEG_SIZE(
  2482.         segPtr->size + segPtr2->size));
  2483.     newPtr->typePtr = &tkTextCharType;
  2484.     newPtr->nextPtr = segPtr2->nextPtr;
  2485.     newPtr->size = segPtr->size + segPtr2->size;
  2486.     strcpy(newPtr->body.chars, segPtr->body.chars);
  2487.     strcpy(newPtr->body.chars + segPtr->size, segPtr2->body.chars);
  2488.     ckfree((char*) segPtr);
  2489.     ckfree((char*) segPtr2);
  2490.     return newPtr;
  2491. }
  2492.  
  2493. /*
  2494.  *--------------------------------------------------------------
  2495.  *
  2496.  * CharDeleteProc --
  2497.  *
  2498.  *    This procedure is invoked to delete a character segment.
  2499.  *
  2500.  * Results:
  2501.  *    Always returns 0 to indicate that the segment was deleted.
  2502.  *
  2503.  * Side effects:
  2504.  *    Storage for the segment is freed.
  2505.  *
  2506.  *--------------------------------------------------------------
  2507.  */
  2508.  
  2509.     /* ARGSUSED */
  2510. static int
  2511. CharDeleteProc(segPtr, linePtr, treeGone)
  2512.     TkTextSegment *segPtr;        /* Segment to delete. */
  2513.     TkTextLine *linePtr;        /* Line containing segment. */
  2514.     int treeGone;            /* Non-zero means the entire tree is
  2515.                      * being deleted, so everything must
  2516.                      * get cleaned up. */
  2517. {
  2518.     ckfree((char*) segPtr);
  2519.     return 0;
  2520. }
  2521.  
  2522. /*
  2523.  *--------------------------------------------------------------
  2524.  *
  2525.  * CharCheckProc --
  2526.  *
  2527.  *    This procedure is invoked to perform consistency checks
  2528.  *    on character segments.
  2529.  *
  2530.  * Results:
  2531.  *    None.
  2532.  *
  2533.  * Side effects:
  2534.  *    If the segment isn't inconsistent then the procedure
  2535.  *    panics.
  2536.  *
  2537.  *--------------------------------------------------------------
  2538.  */
  2539.  
  2540.     /* ARGSUSED */
  2541. static void
  2542. CharCheckProc(segPtr, linePtr)
  2543.     TkTextSegment *segPtr;        /* Segment to check. */
  2544.     TkTextLine *linePtr;        /* Line containing segment. */
  2545. {
  2546.     /*
  2547.      * Make sure that the segment contains the number of
  2548.      * characters indicated by its header, and that the last
  2549.      * segment in a line ends in a newline.  Also make sure
  2550.      * that there aren't ever two character segments adjacent
  2551.      * to each other:  they should be merged together.
  2552.      */
  2553.  
  2554.     if (segPtr->size <= 0) {
  2555.     panic("CharCheckProc: segment has size <= 0");
  2556.     }
  2557.     if (strlen(segPtr->body.chars) != segPtr->size) {
  2558.     panic("CharCheckProc: segment has wrong size");
  2559.     }
  2560.     if (segPtr->nextPtr == NULL) {
  2561.     if (segPtr->body.chars[segPtr->size-1] != '\n') {
  2562.         panic("CharCheckProc: line doesn't end with newline");
  2563.     }
  2564.     } else {
  2565.     if (segPtr->nextPtr->typePtr == &tkTextCharType) {
  2566.         panic("CharCheckProc: adjacent character segments weren't merged");
  2567.     }
  2568.     }
  2569. }
  2570.  
  2571. /*
  2572.  *--------------------------------------------------------------
  2573.  *
  2574.  * ToggleDeleteProc --
  2575.  *
  2576.  *    This procedure is invoked to delete toggle segments.
  2577.  *
  2578.  * Results:
  2579.  *    Returns 1 to indicate that the segment may not be deleted,
  2580.  *    unless the entire B-tree is going away.
  2581.  *
  2582.  * Side effects:
  2583.  *    If the tree is going away then the toggle's memory is
  2584.  *    freed;  otherwise the toggle counts in nodes above the
  2585.  *    segment get updated.
  2586.  *
  2587.  *--------------------------------------------------------------
  2588.  */
  2589.  
  2590. static int
  2591. ToggleDeleteProc(segPtr, linePtr, treeGone)
  2592.     TkTextSegment *segPtr;        /* Segment to check. */
  2593.     TkTextLine *linePtr;        /* Line containing segment. */
  2594.     int treeGone;            /* Non-zero means the entire tree is
  2595.                      * being deleted, so everything must
  2596.                      * get cleaned up. */
  2597. {
  2598.     if (treeGone) {
  2599.     ckfree((char *) segPtr);
  2600.     return 0;
  2601.     }
  2602.  
  2603.     /*
  2604.      * This toggle is in the middle of a range of characters that's
  2605.      * being deleted.  Refuse to die.  We'll be moved to the end of
  2606.      * the deleted range and our cleanup procedure will be called
  2607.      * later.  Decrement node toggle counts here, and set a flag
  2608.      * so we'll re-increment them in the cleanup procedure.
  2609.      */
  2610.  
  2611.     if (segPtr->body.toggle.inNodeCounts) {
  2612.     ChangeNodeToggleCount(linePtr->parentPtr,
  2613.         segPtr->body.toggle.tagPtr, -1);
  2614.     segPtr->body.toggle.inNodeCounts = 0;
  2615.     }
  2616.     return 1;
  2617. }
  2618.  
  2619. /*
  2620.  *--------------------------------------------------------------
  2621.  *
  2622.  * ToggleCleanupProc --
  2623.  *
  2624.  *    This procedure when a toggle is part of a line that's
  2625.  *    been modified in some way.  It's invoked after the
  2626.  *    modifications are complete.
  2627.  *
  2628.  * Results:
  2629.  *    The return value is the head segment in a new list
  2630.  *    that is to replace the tail of the line that used to
  2631.  *    start at segPtr.  This allows the procedure to delete
  2632.  *    or modify segPtr.
  2633.  *
  2634.  * Side effects:
  2635.  *    Toggle counts in the nodes above the new line will be
  2636.  *    updated if they're not already.  Toggles may be collapsed
  2637.  *    if there are duplicate toggles at the same position.
  2638.  *
  2639.  *--------------------------------------------------------------
  2640.  */
  2641.  
  2642. static TkTextSegment *
  2643. ToggleCleanupProc(segPtr, linePtr)
  2644.     TkTextSegment *segPtr;    /* Segment to check. */
  2645.     TkTextLine *linePtr;    /* Line that now contains segment. */
  2646. {
  2647.     TkTextSegment *segPtr2, *prevPtr;
  2648.     int counts;
  2649.  
  2650.     /*
  2651.      * If this is a toggle-off segment, look ahead through the next
  2652.      * segments to see if there's a toggle-on segment for the same tag
  2653.      * before any segments with non-zero size.  If so then the two
  2654.      * toggles cancel each other;  remove them both.
  2655.      */
  2656.  
  2657.     if (segPtr->typePtr == &tkTextToggleOffType) {
  2658.     for (prevPtr = segPtr, segPtr2 = prevPtr->nextPtr;
  2659.         (segPtr2 != NULL) && (segPtr2->size == 0);
  2660.         prevPtr = segPtr2, segPtr2 = prevPtr->nextPtr) {
  2661.         if (segPtr2->typePtr != &tkTextToggleOnType) {
  2662.         continue;
  2663.         }
  2664.         if (segPtr2->body.toggle.tagPtr != segPtr->body.toggle.tagPtr) {
  2665.         continue;
  2666.         }
  2667.         counts = segPtr->body.toggle.inNodeCounts
  2668.             + segPtr2->body.toggle.inNodeCounts;
  2669.         if (counts != 0) {
  2670.         ChangeNodeToggleCount(linePtr->parentPtr,
  2671.             segPtr->body.toggle.tagPtr, -counts);
  2672.         }
  2673.         prevPtr->nextPtr = segPtr2->nextPtr;
  2674.         ckfree((char *) segPtr2);
  2675.         segPtr2 = segPtr->nextPtr;
  2676.         ckfree((char *) segPtr);
  2677.         return segPtr2;
  2678.     }
  2679.     }
  2680.  
  2681.     if (!segPtr->body.toggle.inNodeCounts) {
  2682.     ChangeNodeToggleCount(linePtr->parentPtr,
  2683.         segPtr->body.toggle.tagPtr, 1);
  2684.     segPtr->body.toggle.inNodeCounts = 1;
  2685.     }
  2686.     return segPtr;
  2687. }
  2688.  
  2689. /*
  2690.  *--------------------------------------------------------------
  2691.  *
  2692.  * ToggleLineChangeProc --
  2693.  *
  2694.  *    This procedure is invoked when a toggle segment is about
  2695.  *    to move from one line to another.
  2696.  *
  2697.  * Results:
  2698.  *    None.
  2699.  *
  2700.  * Side effects:
  2701.  *    Toggle counts are decremented in the nodes above the line.
  2702.  *
  2703.  *--------------------------------------------------------------
  2704.  */
  2705.  
  2706. static void
  2707. ToggleLineChangeProc(segPtr, linePtr)
  2708.     TkTextSegment *segPtr;    /* Segment to check. */
  2709.     TkTextLine *linePtr;    /* Line that used to contain segment. */
  2710. {
  2711.     if (segPtr->body.toggle.inNodeCounts) {
  2712.     ChangeNodeToggleCount(linePtr->parentPtr,
  2713.         segPtr->body.toggle.tagPtr, -1);
  2714.     segPtr->body.toggle.inNodeCounts = 0;
  2715.     }
  2716. }
  2717.  
  2718. /*
  2719.  *--------------------------------------------------------------
  2720.  *
  2721.  * ToggleCheckProc --
  2722.  *
  2723.  *    This procedure is invoked to perform consistency checks
  2724.  *    on toggle segments.
  2725.  *
  2726.  * Results:
  2727.  *    None.
  2728.  *
  2729.  * Side effects:
  2730.  *    If a consistency problem is found the procedure panics.
  2731.  *
  2732.  *--------------------------------------------------------------
  2733.  */
  2734.  
  2735. static void
  2736. ToggleCheckProc(segPtr, linePtr)
  2737.     TkTextSegment *segPtr;        /* Segment to check. */
  2738.     TkTextLine *linePtr;        /* Line containing segment. */
  2739. {
  2740.     register Summary *summaryPtr;
  2741.  
  2742.     if (segPtr->size != 0) {
  2743.     panic("ToggleCheckProc: segment had non-zero size");
  2744.     }
  2745.     if (!segPtr->body.toggle.inNodeCounts) {
  2746.     panic("ToggleCheckProc: toggle counts not updated in nodes");
  2747.     }
  2748.     for (summaryPtr = linePtr->parentPtr->summaryPtr; ;
  2749.         summaryPtr = summaryPtr->nextPtr) {
  2750.     if (summaryPtr == NULL) {
  2751.         panic("ToggleCheckProc: tag not present in node");
  2752.     }
  2753.     if (summaryPtr->tagPtr == segPtr->body.toggle.tagPtr) {
  2754.         break;
  2755.     }
  2756.     }
  2757. }
  2758.  
  2759. /*
  2760.  *----------------------------------------------------------------------
  2761.  *
  2762.  * TkBTreeCharsInLine --
  2763.  *
  2764.  *    This procedure returns a count of the number of characters
  2765.  *    in a given line.
  2766.  *
  2767.  * Results:
  2768.  *    The return value is the character count for linePtr.
  2769.  *
  2770.  * Side effects:
  2771.  *    None.
  2772.  *
  2773.  *----------------------------------------------------------------------
  2774.  */
  2775.  
  2776. int
  2777. TkBTreeCharsInLine(linePtr)
  2778.     TkTextLine *linePtr;        /* Line whose characters should be
  2779.                      * counted. */
  2780. {
  2781.     TkTextSegment *segPtr;
  2782.     int count;
  2783.  
  2784.     count = 0;
  2785.     for (segPtr = linePtr->segPtr; segPtr != NULL; segPtr = segPtr->nextPtr) {
  2786.     count += segPtr->size;
  2787.     }
  2788.     return count;
  2789. }
  2790.